应用

剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: 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 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

提示：你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小

思路：

考虑同一窗口中下标（i由于i,j位于同一窗口，且满足上述条件，故知当前窗口最大值必不为nums[i]，可忽略；

故可采用一个严格单调递减的队列来维持遍历的元素（要比较队尾和当前遍历元素，不满足，弹出队尾），且当前窗口最大值为队头元素。
考虑到窗口大小限制，假设队头元素索引i，与当前遍历元素j，有j-i+1>k --> j-i>=k，则二者并不在同一窗口
- 故需要检查队头元素索引与当前遍历元素之间的距离，若不满足条件，则弹出队头
由上述知，需要维持单调队列，且队头队尾均需要操作，故应使用双端单调队列
算法：
设窗口区间为[i,j]，则有。
由题意知，窗口区间前进趋势为[i-1,j-1]->[i,j]即每次滑动，弹出首位元素，压入末尾元素,故依据该特性，应采用双端队列作为该窗口数据结构。
deque:

deque内仅包含窗口内元素->每轮窗口滑动移除[i-1]，需要将deque内元素一同移除。

deque内的元素非严格单调递减->每轮窗口需要压入[j],由于取得最大值，故需要将队列中>nums[j]的元素弹出，再压入nums[j]；

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
 deque<int> dq;
 int N=nums.size();
 if(!N) return {};
 vector<int> ans(N-k+1,0);
 for(int j=0;j<N;j++){
     while(!dq.empty() && dq.back()<nums[j]){
         dq.pop_back();
     }
     dq.push_back(nums[j]);
     int i=j-k+1;
     if(i>=0){
         ans[i]=dq.front();
         if(nums[i]==dq.front()){
             dq.pop_front();
         }
     }
 }
 return ans;
}

单调队列

应用

剑指 Offer 59 - I. 滑动窗口的最大值

思路：

算法：