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

ゝ一纸荒年。 2022-12-10 10:29 152阅读 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 条评论，152人围观）

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

相关阅读

相关滑动窗口最大值——单调队列的实践

一、单调队列的介绍单调队列，即单调递减或单调递增的队列。而且，队首和队尾都可以进行出队操作，但只有队尾可以进行入队操作。它类似于下面这幅图： ![33cbfda4c8

刺骨的言语ヽ痛彻心扉/ 2024年03月31日 10:40/ 0 赞/ 53 阅读

相关【算法题解】23. 「滑动窗口最大值」单调队列解法

文章目录题目题解 Java 代码实现 Go 代码实现复杂度分析 > 这是

约定不等于承诺〃/ 2024年03月24日 17:47/ 0 赞/ 47 阅读

相关 poj2823（滑动窗口，单调队列模板）

Sliding Window <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1200

Bertha 。/ 2024年02月17日 23:23/ 0 赞/ 40 阅读

相关滑动窗口的最大值

vector<int> maxInWindows(const vector<int>& num, unsigned int size) { ve

待我称王封你为后i/ 2023年02月18日 06:28/ 0 赞/ 86 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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