本文主要是介绍239. 滑动窗口最大值/76. 最小覆盖子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
思路：用单调队列处理，滑动窗口的加入元素和移除元素相当于队列的pop和push，找出最大元素相当于单调队列的中最大值，也就是队列的头元素（que.front()）。下一步设计一个队列，包含出队、入队、寻找最大值的操作。
入队：要维护单调队列，当元素入队时，首先和队尾元素比较，如果大于队尾元素，队尾元素出队，直到入队元素小于等于队尾元素的数值为止。
例子如下：通过这种操作可以保持队列中元素单调，滑动窗口最大值就等于队列头元素
出队：其实上面入队操作已经有元素出队了，只需要判断滑动窗口移除元素等于队列首元素时，再将队首元素出队，为什么呢
如下图：第一步到第二步时候元素1需要移除，但在元素3入队时就将1出队了，因为我们需要保持队列单调；第二步到第三步元素3需要移除，此时队首元素出队就可以，再让元素5入队（元素5入队时候会将-1，-3顶出）
最后会发现当前元素需要移除时，要不它就等于队首元素，要不它就在我们自定义入队操作时就出队了。
代码：
class Solution {
private:class Myque{//自定义单调队列public:deque<int> que;void pop(int value){//移除元素if(!que.empty()&&value==que.front()){que.pop_front();}}void push(int value){//加入元素while(!que.empty()&&value>que.back()){//如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。que.pop_back();}que.push_back(value);}int maxvalue() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {Myque que;vector<int> n;for(int i=0;i<k;i++){que.push(nums[i]);}n.push_back(que.maxvalue());//先记录最大值for(int i=k;i<nums.size();i++){que.pop(nums[i-k]);que.push(nums[i]);n.push_back(que.maxvalue());}return n;}
};76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
思路：通过滑动窗口，right移动直到包含t中全部元素，接下来收缩窗口，移动left,始终保持滑动窗口包含t，找到最小的窗口的长度就是答案。
下一步就是解决怎么确定滑动窗口中包含t，我们通过哈希表记录t中元素出现的个数，再记录滑动窗口移动过程中记录t中元素出现个数，再进行比较。
right：对于right而言，每次向右移动之后，先判断加入的元素是否出现在t的哈希表中，如果在，滑动窗口的哈希表中对应的元素个数就加一。
left：如果t中元素出现个数在当前滑动窗口中出现个数一样，就可以收缩left
代码：
class Solution {
public:unordered_map<char,int> tstr,sstr;//两个哈希表bool check()//比较函数{for(auto tchar : tstr){if(tchar.second > sstr[tchar.first]) return false;//注意这里的判断条件是大于//只要sstr中元素的second值不小于tchar中对应元素的second值就行//也就是判断滑动窗口中出现t中元素的个数是否和t的哈希表记录的一样}return true;}string minWindow(string s, string t) {//情况一，t的长的大于sint n1 = s.size(),n2 = t.size();if(n1<n2) return "";int len = INT_MAX;//最小窗口的长度int mleft=0;//最小窗口的左边界int mright=-1;//最小窗口的右边界//构造t的哈希表for(auto tchar : t)++tstr[tchar];int left = 0,right = -1;//滑动窗口的左右两端指针while(right<n1){right++;//右边界移动if(tstr[s[right]]){if(sstr[s[right]]){sstr[s[right]]+=1;//当前元素已经出现过}else{sstr[s[right]]=1;//第一次出现}}while(check()){int m=right-left+1;//当前滑动窗口的长度if(m<len){//更新最小窗口mleft=left;mright=right;len=m;}if(tstr[s[left]]){//左边界的元素在t中sstr[s[left]]-=1;//左边界收缩时就需要减去滑动窗口哈希表中元素出现的次数}left++;//匹配成功才需要收缩左边界}}if (len == INT_MAX) {//如果最小窗口从来没有变化，按题目意思返回空return "";}return s.substr(mleft,len);//截取记录的最小窗口}
};这篇关于239. 滑动窗口最大值/76. 最小覆盖子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
