当前位置：首页 > news >正文

滑动窗口最大值(力扣239)

news 来源：原创 2025/6/9 8:38:19

刚拿到这道题，我们第一反应就是遍历每一个滑动窗口，然后在滑动窗口中遍历找到该窗口的最大值,但是这样的时间复杂度为O(k*n).有没有更简单的方法呢？答案是使用队列。更准确的说是双向队列。下面我将详细讲解一下如何使用双向队列解决这道问题。

在按照滑动窗口的大小遍历数组时，我们可以一边将数据存储到双向队列中，一边要及时弹出数据，保证队列中的数字一定是同一窗口且队列的首个元素一定是该窗口的最大值。那么该如何保证呢？在我们将滑动窗口的末端往后移动一位时，会有一个新窗口的末端数字进入窗口，如果这个末端数字比队列中某些已经存放的数大，那么队列中的这些数一定不可能成为新窗口的最大值，可以全部弹出。同时在滑动窗口移动过程中，我们也需要及时弹出元素，因为每当滑动窗口的起点往后移动一位，窗口起始数字就会移出窗口，自然其也要从队列弹出。但是这个起始数可能一开始就不存在于队列中，因为在将新窗口的末端数字存入队列时，需要通过比大小弹出一些元素，起始数字如果小于该末端数字，它就会被提前弹出。另外还有小的注意点，我写在代码注释中，代码如下：

class Solution {
private:class MyQueue{
public:deque<int> que;//按照文章中说的思路，自定义弹出操作与存入操作void pop(int value){if(que.front() == value){que.pop_front();}}void push(int value){while(!que.empty() && value > que.back()){//要移出的数不一定是第一个数，前面有数挡着，所以得从队列末尾出去，这就体现了双向队列的作用que.pop_back();}que.push_back(value);}int max(){return que.front();}
};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;//开始队列为空，所以我们要先存入第一个滑动窗口的所有数字//方便后续窗口移动过程中的弹出与存入for(int i = 0;i < k;i++){que.push(nums[i]);}result.push_back(que.max());//i用来遍历窗口末端位置，如果用来遍历起始位置，那么末端位置要用加法表示，这样数组访问时会越界for(int i = k;i <= nums.size() - 1;i++){que.pop(nums[i - k]);//用减法表示起始位置，不会数组越界que.push(nums[i]);result.push_back(que.max());}return result;}
};

相关文章：