很多题从后往前遍历和从前往后遍历是两个难度，这个题就是这样，从前往后遍历，后面的还没遍历到，怎么知道比当前的大还是小，而从后往前遍历，后面的遍历过了，当前的只需要判断就可以。

保证栈内元素是从栈底到栈顶升序排列，当前元素比栈顶元素大，说明后面没有比这天高的温度，应该是0天后，当天元素入栈，成为新的最大温度，之后的温度如果比它大，继续成为新的栈顶元素。
如果

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();stack<int>sta;vector<int>res(n);for(int i = n-1; i >= 0; i--){while(!sta.empty() && temperatures[sta.top()] <= temperatures[i]){sta.pop();}res[i] = sta.empty()? 0 : sta.top()-i;sta.push(i);}return res;}
};

循环数组注意要用取余来实现
因为是循环数组， 所以要考虑更多，简单的说就是之前我们只考虑每个元素的后面就行了，现在循环数组的话他前面的元素有可能成为它的下一个更大元素，所以我们在一轮完了建好栈了还需要再遍历一轮。

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();stack<int>sta;vector<int>res(n,-1);for(int i = 2*n-1; i >= 0; i--){while(!sta.empty() && nums[sta.top()] <= nums[i%n]){sta.pop();}res[i%n] = sta.empty()? -1 : nums[sta.top()];sta.push(i%n);}return res;}
};

这里感觉要用两个栈来做，后面发现可以一个栈用pair保存两个值，价钱以及这个价钱跨度多少 其实直接一个键值对就好了，pair非常好用，最近用到好几次

第二次复习有点卡思路，保证单调栈不会漏解，就是在出栈的时候，当前元素的天数应该加上出栈元素的天数，而不能直接像之前那样得出来。
70 60 50 80
在80的判定阶段，应该是+1+1+1
单调栈变为
80
如果此时来了90.是+4
单调栈变为
90

就是这个单调栈是阶段性收容

60 50 40 30 70 50 40 60 40 30 20 50
最后会变成
70 60 50 对应的天数是
5 3 4
如果此时来一个100
直接做5+3+4就可以了

这道题就是一个阶段性单调栈。 ，每一次调整后的栈顶元素是代表某一段，有点像我们写代码时候可以把一个函数的代码收起放下，就这个感觉。

class StockSpanner {
public:stack<pair<int,int>>sta;StockSpanner() {sta = stack<pair<int,int>>();}int next(int price) {pair<int,int>p(price,1);while(!sta.empty() && price >= sta.top().first){p.second += sta.top().second;sta.pop();}sta.push(p);return p.second;}
};

高频考点，笔试面试见过好多次

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int>left(n,0);stack<int>sta;for(int i = 0; i < n; i++){while(!sta.empty() && heights[sta.top()] >= heights[i]){sta.pop();}if(sta.empty()){left[i] = -1;}else{left[i] = sta.top();}sta.push(i);}sta = stack<int>();vector<int>right(n,0);for(int i = n-1; i >= 0; i--){while(!sta.empty() && heights[sta.top()] >= heights[i]){sta.pop();}if(sta.empty()){right[i] = n;}else{right[i] = sta.top();}sta.push(i);}int res = 0;for(int i = 0; i < n; i++){res = max(res,(right[i]-left[i]-1)*heights[i]);}return res;}
};

第五遍还是出现了卡顿
这里的-1和n怎么来的，我们的左右数组里存的是不满足的值
1 3 1
3的左右数组是0， 2
在减的时候应该是 2-0 再 - 1不是-2，答案就是3 * 1;
因为单独一个也是一个矩形
3 1 3中1为保持统一，对应左右数组-1，3
3 - -1 -1就是3 答案就是1* 3

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int>left(n,0);vector<int>right(n,0);stack<int>sta;for(int i = 0; i < n; i++){while(!sta.empty() && heights[i] <= heights[sta.top()]){sta.pop();}//调整之后的sta.top()是第一个比当前高度小的矩形，也就是不满足的矩形//所以在出现全部小于的情况下，0是满足的，栈为空的我们要赋值-1，要和上面保持统一left[i] = sta.empty()? -1 : sta.top();sta.push(i);}sta = stack<int>();for(int i = n-1; i >= 0; i--){while(!sta.empty() && heights[i] <= heights[sta.top()]){sta.pop();}//调整之后的sta.top()是第一个比当前高度小的矩形，也就是不满足的矩形//所以在出现栈为空也就是之前栈内元素全部小于当期矩形的情况下我们要赋值n，要和上面保持统一//在栈为空的情况下，n是满足的，n-1才是不满足的//我们的两个数组left和right都是保存的第一个 不满足的下标right[i] = sta.empty()? n : sta.top();sta.push(i);}int res = 0;for(int i = 0; i < n; i++){res =max(res,(right[i]-left[i]-1) * heights[i]);}return res;}
};

差分数组d[i] = num[i]-num[i-1]
差分数组的作用就是忽略中间的变化，同增同减就可以认为没有变化
这道题里原数组是
0 0 0 0
差分数组
0 0 0 0
当对0到2的航班订2个位置
原数组变化是
2 2 2 0
而差分数组只需要变成
2 0 0 -2
差分数组又可以推导出原数组
2 2+0 2+0+0 2+0+0+（-2）
因为差分数组变化简单，所以用差分数组

class Solution {
public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {vector<int> nums(n);for (auto& booking : bookings) {nums[booking[0] - 1] += booking[2];if (booking[1] < n) {nums[booking[1]] -= booking[2];}}for (int i = 1; i < n; i++) {nums[i] += nums[i - 1];}return nums;}
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/corporate-flight-bookings/solution/hang-ban-yu-ding-tong-ji-by-leetcode-sol-5pv8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个题就是：
先死命的加，直到加超了
再死命的减
再死命的加
再死命的减
加减之间，滑动窗口移动，就解决问题了
比较困惑的是，这样真能保证不遗漏组合可能性吗

比如 1 1 2 3 2 1 1 1 2 3 4 这个数组，要求和不能大于7求最大连续长度
按上面思路滑动窗口变化过程：
1 maxlen = 1
1 1 maxlen = 2
1 1 2 maxlen = 3
1 1 2 3 maxlen = 4
1 1 2 3 2停下来
按思路是减start
即
1 2 3 2
2 3 2
这样只考虑两种情况
那其他情况有没有被遗漏呢
先看1 1 2 3肯定是满足的，那1 1 2 3内的任意子串也是符合条件的
1 1 2 3 2不符合
1 1 2 3符合
只能去掉第一个看1 2 3 2是否符合

class Solution {
public:int equalSubstring(string s, string t, int maxCost) {int n = s.size();vector<int>diff(n);for(int i = 0; i < s.size(); i++){diff[i] = abs(s[i] - t[i]);}int end = 0; int start = 0;int maxlen = 0;int len = 0;while(end < n){while(end < n && len <= maxCost){maxlen = max(maxlen,end-start);len += diff[end];end++;}while(start < n && len > maxCost){len -= diff[start];start++;}maxlen = max(maxlen,end-start);}return maxlen;}
};

换个题目就不会了

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;int start = 0, end = 0;int sum = 0;while (end < n) {sum += nums[end];while (sum >= s) {ans = min(ans, end - start + 1);sum -= nums[start];start++;}end++;}return ans == INT_MAX ? 0 : ans;}
};

主要是判断前后，就是差一个坐标就错了，for循环while循环做不到实时更新检查是否满足，所以要么加break，要么就是改变在判断之前，循环体内可以放心变更。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int zeronum = 0;int onenum = 0;int end = 0;int start = 0;int maxOnenum = 0;while(end < n){if(nums[end] == 0){zeronum++;}if(zeronum <= k){maxOnenum = max(maxOnenum,end -start + 1);}while(start < n &&zeronum > k){if(nums[start] == 0){zeronum--;}start++;}maxOnenum = max(maxOnenum,end -start + 1);end++;}return maxOnenum;}
};

目前用哈希表移除做，时间复杂度较高容易理解

class Solution {
public:int lengthOfLongestSubstringKDistinct(string s, int k) {int n = s.size();int start = 0;int end = 0;unordered_map<char,int>map;int maxSubstr = 0;while(end < n){map[s[end]]++;if(map.size() <= k){maxSubstr = max(maxSubstr,end - start + 1);}while(map.size() > k){map[s[start]]--;if(map[s[start]] == 0)map.erase(s[start]);start++;}maxSubstr = max(maxSubstr,end - start + 1);end++;}return maxSubstr;}
};

维护哈希表下标做

class Solution {
public:int diffCharNum(unordered_map<char, int>& window){ //统计滑动窗口中不同字符的个数int count = 0;for(auto win : window){count += win.second >= 1 ? 1 : 0;}return count;}int lengthOfLongestSubstringKDistinct(string s, int k) {int n = s.size(), maxLen = 0;int left = 0, right = 0;unordered_map<char, int> window; //字符及其次数while(right < n){window[s[right]]++;while(diffCharNum(window) > k){window[s[left]]--;left++;}maxLen = max(maxLen, right - left + 1);right++;}return maxLen;}
};

这个做出来还是非常有成就感的

class Solution {
public:int minSwaps(vector<int>& data) {int n = data.size();int onenum = 0;for(int i = 0; i < n; i++){if(data[i] == 1){onenum++;}}int zeronum = 0;//当前字符串0数目int curonenum = 0;//当前字符串1数目int begin = 0;int end = 0;int minCount = INT_MAX;while(end < n){if(data[end] == 1){curonenum++;}else{zeronum++;}if(onenum - curonenum == zeronum){minCount = min(zeronum,minCount);}while(onenum - curonenum <= zeronum){if(data[begin] == 1){curonenum--;}else{zeronum--;}begin++;}if(onenum - curonenum == zeronum){minCount = min(zeronum,minCount);}end++;}return minCount;}
};

class Solution {
public:int numKLenSubstrNoRepeats(string s, int k) {int n = s.size();unordered_map<char,int>map;if(s.size() < k)return 0;int end = 0;int begin = 0;int res = 0;while(end < n){map[s[end]]++;if(end > k-1){map[s[begin]]--;if(map[s[begin]] == 0){map.erase(s[begin]);}begin++;}res  += (map.size() == k);end++;}return res;}
};

模板套就完事，这时间复杂度不行呀

class Solution {
public:int lengthOfLongestSubstringTwoDistinct(string s) {int n = s.size();int end = 0;int begin = 0;int maxLen = 0;unordered_map<char,int>map;while(end < n){map[s[end]]++;if(map.size() <= 2){maxLen = max(maxLen,end-begin+1);}while(map.size() > 2){map[s[begin]]--;if(map[s[begin]] == 0){map.erase(s[begin]);}begin++;}maxLen = max(maxLen,end-begin+1);end++;}return maxLen;}
};

这里有个概念转换，题目叫我们求连续子数组的和，我们把它转换成求两个连续数组之差，从而用前缀和加哈希来做
mp[0] = 1，0是前缀和为0，1是前缀和为0出现1次，主要是存在
1 1 1 k = 2这样的用例
前缀和数组是1 2 3
2应该是满足题意的，但这里2 - 2 = 0，哈希表里没有，所以我们加一个mp[0] = 1,理解成没有任何数相加，就是0

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();unordered_map<int,int>mp;int pre = 0;int sum = 0;int res = 0;mp[0] = 1;for(auto num : nums){pre += num;if(mp.count(pre - k)){res += mp[pre-k];}mp[pre]++; }return res;}
};

这里要注意我们要刻意保留最早出现的那个可行解，因为它是觉得最后是否满足条件的决定因素，只要有一个满足数组长度大于1就可以了，而我们只要减去最早出现的那个如果它大于1，就保证有一个正确答案，可以返回true，如果它都不大于1，那肯定后面的也不行

class Solution {
public:bool checkSubarraySum(vector<int>& nums, int k) {int n = nums.size();unordered_map<int,int>mp;int pre = 0;mp[0] = -1;for(int i = 0; i < n; i++){pre += nums[i];if(mp.count(pre%k)){if(i - mp[pre%k] > 1){return true;}}else mp[pre%k] = i;}return false;}
};

注意这个和之前区别是加入了负数，负数取模不太一样
c++里涉及负数的取模，余数符号与被除数符号保持一致。

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int n = nums.size();unordered_map<int,int>mp;int pre = 0;int res = 0;mp[0] = 1;for(int i = 0; i < n; i++){pre += nums[i];int modulus = (pre % k + k) % k;if(mp.count(modulus)){res += mp[modulus];}mp[modulus]++;}return res;}
};

就是一个树，可以理解成26叉树
搜索的时侯看是否为空
比如先插入word
这时候有四层
w 下标‘w’-‘a’
o
r
d
再插入worc
第一层下标为w-a的不为空
然后看w-a下面的26叉对应的o-a是否为空
一依次往下

class Trie {
private:vector<Trie*> children;bool isEnd;Trie* searchPrefix(string prefix) {Trie* node = this;for (char ch : prefix) {ch -= 'a';if (node->children[ch] == nullptr) {return nullptr;}node = node->children[ch];}return node;}public:Trie() : children(26), isEnd(false) {}void insert(string word) {Trie* node = this;for (char ch : word) {ch -= 'a';if (node->children[ch] == nullptr) {node->children[ch] = new Trie();}node = node->children[ch];}node->isEnd = true;}bool search(string word) {Trie* node = this->searchPrefix(word);return node != nullptr && node->isEnd;}bool startsWith(string prefix) {return this->searchPrefix(prefix) != nullptr;}
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第一种解法，暴力遍历，用哈希表存储所有单词
然后遍历每个单词的后缀，如果出现后缀与哈希表内单词相同，就移除哈希表内的单词
最后计算没有被移除的单词总长度，注意加#

class Solution {
public:int minimumLengthEncoding(vector<string>& words) {unordered_set<string> good(words.begin(), words.end());for (const string& word: words) {for (int k = 1; k < word.size(); ++k) {good.erase(word.substr(k));}}int ans = 0;for (const string& word: good) {ans += word.size() + 1;}return ans;}
};

struct Trie {unordered_map<char, Trie *> children;
};class Solution {
public:string replaceWords(vector<string>& dictionary, string sentence) {Trie *trie = new Trie();for (auto &word : dictionary) {Trie *cur = trie;for (char &c: word) {if (!cur->children.count(c)) {cur->children[c] = new Trie();}cur = cur->children[c];}cur->children['#'] = new Trie();}vector<string> words = split(sentence, ' ');for (auto &word : words) {word = findRoot(word, trie);}string ans;for (int i = 0; i < words.size() - 1; i++) {ans.append(words[i]);ans.append(" ");}ans.append(words.back());return ans;}vector<string> split(string &str, char ch) {int pos = 0;int start = 0;vector<string> ret;while (pos < str.size()) {while (pos < str.size() && str[pos] == ch) {pos++;}start = pos;while (pos < str.size() && str[pos] != ch) {pos++;}if (start < str.size()) {ret.emplace_back(str.substr(start, pos - start));}}return ret;}string findRoot(string &word, Trie *trie) {string root;Trie *cur = trie;for (char &c : word) {if (cur->children.count('#')) {return root;}if (!cur->children.count(c)) {return word;}root.push_back(c);cur = cur->children[c];}return root;}
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/replace-words/solution/dan-ci-ti-huan-by-leetcode-solution-pl6v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:// 按照区间右边界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1; // 记录非交叉区间的个数int end = intervals[0][1]; // 记录区间分割点for (int i = 1; i < intervals.size(); i++) {if (end <= intervals[i][0]) {end = intervals[i][1];count++;}}return intervals.size() - count;}
};

这道题就是读题，不是叫你模拟，看似情况很多，一个分类讨论，发型只有两种情况，注意最后返回的是最小交换次数

class Solution {
public:int minimumSwap(string s1, string s2) {int n = s1.size();int cnt1 = 0;int cnt2 = 0;for(int i = 0; i < n; i++){if(s1[i] == 'x' && s2[i] == 'y'){cnt1++;}else if(s1[i] == 'y' && s2[i] == 'x'){cnt2++;}}//想组成s1 = "xx", s2 = "yy"需要2个cnt1或者 s1 = "yy"，s2 = "xx"需要两个cnt2//想组成s1 = "xy", s2 = "yx"需要1个cnt1和一个cnt2  或者组成 s1 = "yx"，s2 = "xy"也需要一个cnt1加一个cnt2//所以在组合完毕后，cnt1和cnt2必须都为0，不能遗留下来//所以要求是 cnt1%2 == 0&&cnt2%2 == 0  || cnt1+cnt2 % 2 == 0 其实应该是大减小是偶数，这里用性质，减偶数和加偶数一样//可以看出第二个条件包含第一个if((cnt1+cnt2)%2 == 0){return cnt1/2 + cnt2/2 + cnt1%2*2;//题目求的是最小交换次数，第一种组合只需要交换一次，第二种交换2次，优先第一次，剩余的再第二次//优先第二种的话应该是 //return min(cnt1,cnt2)*2 + (max(cnt1,cnt2) - min(cnt1,cnt2))/2;}else return -1;}
};

class Solution {
public:int leastInterval(vector<char>& tasks, int n) {unordered_map<char, int> freq;for (char ch: tasks) {++freq[ch];}// 任务总数int m = freq.size();vector<int> nextValid, rest;for (auto [_, v]: freq) {nextValid.push_back(1);rest.push_back(v);}int time = 0;for (int i = 0; i < tasks.size(); ++i) {++time;int minNextValid = INT_MAX;for (int j = 0; j < m; ++j) {if (rest[j]) {minNextValid = min(minNextValid, nextValid[j]);}}time = max(time, minNextValid);int best = -1;for (int j = 0; j < m; ++j) {if (rest[j] && nextValid[j] <= time) {if (best == -1 || rest[j] > rest[best]) {best = j;}}}nextValid[best] = time + n + 1;--rest[best];}return time;}
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode-solution-ur9w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个中间是需要更新跳跃次数的，一个最大距离内遍历完再将跳跃次数加一，最大距离保持持续更新，但跳跃次数的最大距离是分块更新的

class Solution {
public:int jump(vector<int>& nums) {int maxPos = 0, n = nums.size(), end = 0, step = 0;for (int i = 0; i < n - 1; ++i) {maxPos = max(maxPos, i + nums[i]);if (i == end) {end = maxPos;++step;}}return step;}
};

还是读懂题意，是让你求摆动序列吗，其实不是，是让你找有多少个峰，也就是极值，最后你要做的就是把极值全部留下
极值特点是啥，左右差值异号
1 2 1就是一个摆动序列

[1,17,5,10,13,15,10,5,16,8]
16 -12 5 3 2 -5 11 -8
16 -12中间的保留
-12 5之间的保留
5 3，3 2之间的去掉
2 -5之间保留
-5 11，11 -8之间的都保留
保留了5个峰
17 5 15 5 16
最后摆动序列长度要加上首尾

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if (n < 2) {return n;}int prevdiff = nums[1] - nums[0];int ret = prevdiff != 0 ? 2 : 1;for (int i = 2; i < n; i++) {int diff = nums[i] - nums[i - 1];if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {ret++;prevdiff = diff;}}return ret;}
};

[3,3,3,1,3,3,1]
注意题解中判断条件，是限制一边的diff严格不为0
这样就可以把1 3 3这种情况排除掉

第七八周内另开新篇