相关问题：496. Next Greater Element I
问题：
给定一个数组，和一个大小为k的滑动窗口，
求窗口范围内的最大值依次是多少。
Example 1: Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [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 Example 2: Input: nums = [1], k = 1 Output: [1] Example 3: Input: nums = [1,-1], k = 1 Output: [1,-1] Example 4: Input: nums = [9,11], k = 2 Output: [11] Example 5: Input: nums = [4,-2], k = 2 Output: [4] Constraints: 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length
解法：Monotonic queue（单调队列）
参照：496. Next Greater Element I
本问题使用，单调递增队列解决。
问题中，滑动窗口依次向右移动一个，
即左边界-1，右边界+1.
而这种变化，要求的最大值，
- 若非左边界，则只需求max(原最大值，新加右边界)
- 若是左边界，则需要遍历窗口，找到下一个最大值，然后求max(下一个最大值，新加右边界)
第二种情况，会使复杂度*N
这里，我们可以利用单调递增队列，来保存窗口中的值，
- 队头->队尾
- 大->小（单调变化，删掉两个大值中间的小值）
- index：小->大
那么，我们每次要求的最大值即是，队头 deque.front
而当我们移动窗口后，这个队头若==左边界，
那么就删除队头:deque.pop_front()
这样，剩下的队头，为剩下的最大值。
代码参考：
1 class Solution { 2 public: 3 vector<int> maxSlidingWindow(vector<int>& nums, int k) { 4 vector<int> res; 5 deque<int> dq; 6 int n=nums.size(); 7 for(int i=0; i<n; i++) { 8 if(!dq.empty() && dq.front()==(i-k)) dq.pop_front(); 9 //dq.front() must be the smallest idx in deque. 10 //cause only the latter idx can be add behind dq.front 11 while(!dq.empty() && nums[dq.back()]<=nums[i]) { 12 dq.pop_back(); 13 } 14 dq.push_back(i); 15 if(i>=(k-1)) res.push_back(nums[dq.front()]); 16 } 17 return res; 18 } 19 };