滑动窗口最大值

给定一个数组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 ------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
示例 2：
输入：nums = [1], k = 1
输出：[1]

这题可以用一个单调队列来解决。一般步骤如下：

1. 入（元素进入队尾，同时维护队列单调性）
2. 出（元素离开队首）
3. 记录/维护答案（根据队首）

这题可以通过维护一个单调递减的单调队列来实现。

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> que;
    for(int i=0;i<nums.size();i++){
      //1.入队，维护单调性
      while(!que.empty() && nums[que.back()] <= nums[i]){
        que.pop_back();
      }
      que.push_back(i);
      //2.出队
      if(i-que.front() >= k){
        que.pop_front();
      }
      //3.记录答案
      if(i >= k-1 ){
        res.push_back(nums[que.front()]);
      }
    }
    return res;
  }
};

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13