单调队列模板(滑动窗口的最大值)

ゝ一纸荒年。 2022-12-10 10:29 160阅读 0赞

有一个数组为1 3 -1 -3 5 3 6 7\],有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

窗口中一次性只能存在k个数字

每次滑动窗口向右移动一个位置,现在要求输出每次窗口中的最小值

例如第一次: 1 3 -1 窗口中的最小值为-1

第二次:3 -1 -3 窗口中的最小值为-3

第三次:-1 -3 5 窗口中的最小值为-3

第四次 -3 5 3 窗口中的最小值为-3 依次类推

我们的做法是维护一个单调队列,并保持队列的单调递增性,这样每次队头元素就是这个窗口中的最小值

第一次,1进队,最小元素为1

第二次,3进队,没有破坏队列的单调性,队列为\[1,3\],最小元素1

第三次,-1进队,1比-1大,-1出队,3比-1大,3出队 此时最小元素为-1

第四次,-3进队,-1比-3大,-1出队,此时最小元素为-3

第五次,5进队,队列为\[-3,5\] 维持了单调性,最小元素为-3

第六次,3进队,5比3大,不满足单调性,5出队,\[-3,3\]保持了单调性,

第七次,-3被滑出窗口,6进队,\[3,6\]保持了单调性

第八次,7入队,\[3,6,7\]保持了单调性

算法结束

#include <iostream>
    using namespace std;
    const int N = 1000010;
    int q[N],a[N],hh = 0,tt = -1;
    int n,k;
    
    int main(){
        cin >> n >> k;
        for(int i = 0;i < n;++i) scanf("%d",&a[i]);
        
        for(int i = 0;i < n;++i){
            if(hh <= tt && i - k + 1 > q[hh]) hh++; //窗口滑动
            while(hh <= tt && a[q[tt]] >= a[i]) tt--; //保持单调性
            q[++tt] = i;  //入队
            if(i >= k - 1) printf("%d ",a[q[hh]]); //队列中满足k个元素时才输出
            
        }
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 239滑动窗口最大值

一思路一开始我想用个移动的列表记录，没想到效率太低二代码 class Solution: def maxSlidingWindo

小灰灰/ 2023年07月18日 14:01/ 0 赞/ 46 阅读

相关 LeetCode239. 滑动窗口最大值【优先队列】

难度：困难题目描述： > 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k > 个数字。滑动

港控/mmm°/ 2023年01月22日 12:53/ 0 赞/ 16 阅读

相关 239. 滑动窗口最大值

参考： [剑指 Offer 59 - I. 滑动窗口的最大值][Offer 59 - I.] [Offer 59 - I.]: https://blog.csdn.n

╰半夏微凉°/ 2022年12月12日 01:52/ 0 赞/ 234 阅读

相关单调队列模板(滑动窗口的最大值)

有一个数组为1 3 -1 -3 5 3 6 7\],有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。窗口中一次性只能存在k个数字每次滑动窗口向右移动一个位置,现

ゝ一纸荒年。/ 2022年12月10日 10:29/ 0 赞/ 161 阅读

相关【每日一题】队列系列(1) —— 滑动窗口最大值

一、题目描述 > 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动

喜欢ヅ旅行/ 2022年11月06日 11:55/ 0 赞/ 127 阅读

相关力扣-239题滑动窗口最大值（C++）- 有价值+单调队列

题目链接：[https://leetcode-cn.com/problems/sliding-window-maximum/][https_leetcode-cn.com_pr

向右看齐/ 2022年09月12日 07:47/ 0 赞/ 217 阅读

相关 239. 滑动窗口最大值（优先队列）

题目重述给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

痛定思痛。/ 2022年09月11日 13:14/ 0 赞/ 173 阅读

相关 LeetCode 滑动窗口最大值【滑动窗口】

1 滑动窗口最大值给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移

秒速五厘米/ 2022年09月10日 11:26/ 0 赞/ 206 阅读

相关 LeetCode-239. 滑动窗口最大值(单调队列)

[LeetCode-239. 滑动窗口最大值][LeetCode-239.] 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可

朴灿烈づ我的快乐病毒、/ 2022年04月24日 07:04/ 0 赞/ 189 阅读

相关 154. 滑动窗口【单调队列】

滑动窗口问题描述给定一个大小为n≤106的数组。有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。您只能在窗口中看到k个数字。每次滑动窗口向右

妖狐艹你老母/ 2022年01月06日 07:27/ 0 赞/ 232 阅读