LeetCode 239

概述

• https://leetcode-cn.com/problems/sliding-window-maximum/
• 给定一个整形数组，固定滑动窗口长度，窗口从左到右每次滑动一个元素，返回每次窗口的最大值

思路1

• 滑动窗口的模拟，容易想到使用队列

• 难点是如何找到每次窗口的最大值，如果在次窗口中暴力求解，O（N^2）会超时。考虑最好在每次窗口滑动时，就能确定最大值。

• 找最大值需要比较排序，考虑优先队列可以确保每次最大值都在窗口的第一个。问题又来了，因为排序后数字的位置改变，每次移出窗口的数不一定是优先队列中最左边的数，如何来确认呢？

• 因为我们只需要找到每次的最大值，不需要关心队列里到底有哪些数字。而最大值永远在优先队列的最左边，我们只需判断每次移动后，该最大值是否被移出队列即可。

  每次移出窗口的数组下标是确定的，所以我们可以同时保存值和下标，这样就算排序后数组位置改变，我们还是可以确定是否目前的最大值是否被移出。

  class Solution {
  public:
      vector<int> maxSlidingWindow(vector<int>& nums, int k) {
          int n = nums.size();
          priority_queue<pair<int, int> > q;		//同时保存值和下标
          for (int i = 0; i < k; ++i) {
              q.emplace(nums[i], i);	
          }
          vector<int> ans = {q.top().first};
          for (int i = k; i < n; ++i) {
              q.emplace(nums[i], i);
              while (q.top().second <= i - k) {	//i-k之前的数都是应该被移出的
                  q.pop();
              }
              ans.push_back(q.top().first);
          }
          return ans;
      }
  };
  //时间：O(nlogn) 	空间：O(n)

思路2

• 其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了

  • 如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i < j），并且 i 对应的元素不大于 j 对应的元素（nums[i]≤nums[j]）
  • 当窗口右移时，如果 i 还在窗口，j 一定在窗口，且此时最大值不可能是nums[i]
  • 按照上述分析，所有num[i]就可以不用保存在队列中了

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result;
        deque<int> dq;
        for(int i=0;i<k;i++){
            while(!dq.empty()&&nums[i]>dq.back()){	//按上述分析 保存特定顺序下的窗口元素
                dq.pop_back();
            }
            dq.emplace_back(nums[i]);
        }
       result.push_back(dq.front());	//第一个窗口的最大值
       for(int i=k;i<n;i++){
        if(!dq.empty()&&nums[i-k]==dq.front())	//num[i-k]是窗口该移出的元素，判断是否等于队列最前面的值，如果相等则表示其会被移出窗口
            dq.pop_front();			why???
        while(!dq.empty()&&nums[i]>dq.back())	//只要添加数字进窗口都进行该操作
            dq.pop_back();
            dq.emplace_back(nums[i]);
        result.emplace_back(dq.front());    //每次移动完后，队列最前面的值，就是此时窗口的最大值  why??
       }
       return result;
    }
};

• 有两处问题需要考虑