【LeetCode 26】239.滑动窗口最大值

简介: 【LeetCode 26】239.滑动窗口最大值

一、题意

二、思考过程

这是使用 单调队列的经典题目。

**单调队列:**即单调递减或单调递增的队列。

这个队列需要我们自己实现,可以用 deque 放进队列窗口的元素随着窗口的移动,队列一进一出,每次移动之后,队列告诉我们里面最大值是什么:

class MyQueue {
public:
    //滑动窗口中移除的元素数值
    void pop(int value) {
    }
    
    //滑动窗口添加的元素数值
    void push(int value) {
    }
    
    //返回滑动窗口中的最大值
    int front() {
        return que.front();
    }
};
  • pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作。
  • push(value):如果push的元素value大于入口元素的值,那么就将队列入口的元素弹出。

保持如上规则,每次窗口移动的时候,只要问 que.front()就可以返回当前窗口的最大值。

class Solution {
private:
    class MyQueue
    {//单调队列(从大到小)
        public:
            deque<int> que;//使用deque来实现单调队列
            /*
            每次弹出栈的时候,比较当前要弹出的数值是否等于队列出口元
            素的数值如果相等则弹出,同时pop之前还要判断队列当前
            是否为空
            */
            void pop(int value)
            {
                if(!que.empty()&&value==que.front())
                {
                    que.pop_front();
                }
            }
            /*
            如果push的数值大于入口元素的数值,那么就将队列后端的数据弹出
            直到push的数值小于队列入口元素的数值为止。
            这样就保持了队列里的数值是单调从大到小了。
            */
            void push(int value)
            {
                while(!que.empty()&&value>que.back())
                {
                    que.pop_back();
                }
                que.push_back(value);
            }
            /*
            查询当前队列的最大值,直接返回队列前端也就是front就可以了
            */
            int front()
            {
                return que.front();
            }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for(int i=0;i<k;i++)//记录前k元素放进队列
        {
            que.push(nums[i]);
        }
        result.push_back(que.front());//result 记录前k元素的最大值
        for(int i=k;i<nums.size();i++)
        {
            que.pop(nums[i-k]);//滑动窗口移除最前面的元素
            que.push(nums[i]);//滑动窗口前加入最后面的元素
            result.push_back(que.front());//记录对应的最大值
        }
        return result;
    }
};


目录
相关文章
|
7月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
2月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
23 0
|
4月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
37 0
|
6月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
34 1
|
6月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
6月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
47 0
|
6月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
6月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串