代码随想录 栈与队列 test 6

239. 滑动窗口最大值 - 力扣（LeetCode）

每次只取窗口中最大值，这个最大值可能在后面的滑动中保持不变，而比最大值小的值且在最大值之前出现的值没必要保留，因此可以通过单调队列利用这个特性。

这个单调队列具有如下性质:

1.队头始终为当前队列的最大值

2.队列具有单调性，队尾为最小值

因此，用三个函数实现题目要求。

pop()，检查当前滑动窗口最后一个元素是否为单调队列的队头，若不是则不用管，这说明该元素不是当前单调队列的最大值，在这之前就已经被丢出单调队列中。

push()，将当前滑动窗口的第一个元素加入单调队列中，把队列中小于该元素的值全部丢出队列。

getmax()，单调队列的队头即为最大值。

class Solution {
private:
    class MyQueue{
    public:
    deque<int> queue;
    
    void pop(int num){
        if(!queue.empty() && num == queue.front())
            queue.pop_front();
    }

    void push(int num){
        while(!queue.empty() && num > queue.back()){
            queue.pop_back();
        }
        queue.push_back(num);
    }

    int getMax(){
        return queue.front();
    }
    };
public:
    MyQueue queue;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        
        for(int i = 0; i < k; i++){
            queue.push(nums[i]);
        }

        res.push_back(queue.getMax());

        for(int i = k; i < nums.size(); i++){
            queue.pop(nums[i - k]);
            queue.push(nums[i]);
            res.push_back(queue.getMax());
        }

        return res;
    }
};

原文地址：https://blog.csdn.net/m0_73941517/article/details/145328926

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！