原题链接

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

  1. Example 1:
  2. Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
  3. Output: [3,3,5,5,6,7]
  4. Explanation: 
  5. Window position                Max
  6. ---------------               -----
  7. [1  3  -1] -3  5  3  6  7       3
  8.  1 [3  -1  -3] 5  3  6  7       3
  9.  1  3 [-1  -3  5] 3  6  7       5
  10.  1  3  -1 [-3  5  3] 6  7       5
  11.  1  3  -1  -3 [5  3  6] 7       6
  12.  1  3  -1  -3  5 [3  6  7]      7

进阶：

你能在线性时间复杂度内解决此题吗？

代码 1 the use of “deque”

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

image.png

代码 2 数组 模拟 列表

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        int n = nums.size();
        int q[n+10];
        int hh = 0, tt = -1;
        for(int i=0; i<n; i++){
            if(hh <= tt && i-k+1 > q[hh]) hh++;

            while(hh <= tt && nums[i] >= nums[q[tt]]) tt--;
            q[++tt] = i;

            if(i >= k-1) ans.push_back(nums[q[hh]]);
        }
        return ans;
    }
};

image.png