首页 > 编程语言 >单调栈与单调队列算法总结

单调栈与单调队列算法总结

时间:2023-12-05 21:14:21浏览次数:41  
标签:队列 ++ tt hh int 算法 printf 单调

单调栈

知识概览

  • 单调栈最常见的应用是找到每一个数离它最近的且比它小的数。
  • 单调栈考虑的方式和双指针类似,都是先想一下暴力做法是什么,然后再挖掘一些性质如单调性,最终可以把目光集中在比较少的状态中,从而达到降低时间复杂度的作用,都是算法优化的一种手段。
  • 对于x < y, a_x \geqslant a_y的情况,a_y更有可能是答案,因此将a_x删掉。最终,剩下的是严格单调上升的序列。

 

例题展示

题目链接

https://www.acwing.com/problem/content/832/

代码

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int stk[N], tt;

int main()
{
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt--;
        if (tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        
        stk[++tt] = x;
    }
    
    return 0;
}

 

单调队列

知识概览

  • 单调队列最经典的一个应用是求一下滑动窗口里的最大值或最小值。
  • 用数组模拟栈和队列的效率更高,这里用数组模拟。

 

例题展示

题目链接

https://www.acwing.com/problem/content/156/

代码

#include <iostream>

using namespace std;

const int N = 1000010;

int n, k;
int a[N], q[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    int hh = 0, tt = -1;
    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]]);
    }
    puts("");
    
    hh = 0, tt = -1;
    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]]);
    }
    puts("");
    
    return 0;
}

 

标签:队列,++,tt,hh,int,算法,printf,单调
From: https://www.cnblogs.com/ykycode/p/17878159.html

相关文章

  • 代码随想录算法训练营第六天| 454.四数相加 15.三数之和 18.四数之和
    LeetCode454.四数相加题目链接:LeetCode454思路: 将两个数组中的数存放到一个map中,用另外两个数组的值在map中去减 classSolution{public:intfourSumCount(vector<int>&A,vector<int>&B,vector<int>&C,vector<int>&D){unordered_map&l......
  • 扩展欧几里得算法
    扩展欧几里得算法裴蜀定理(Bézout'slemma)定义设\(a,b\)是不全为零的整数,对任意整数\(x,y\),满足\(\gcd(a,b)\midax+by\),且存在整数\(x,y\),使得\(ax+by=\gcd(a,b)\).证明对于第一点由于\(\gcd(a,b)\mida,\gcd(a,b)\midb\)所以\(\gcd(a,b)\midax,\gcd(a,b)\mid......
  • 文心一言 VS 讯飞星火 VS chatgpt (150)-- 算法导论12.2 6题
    六、用go语言,考虑一棵二叉搜索树T,其关键字互不相同。证明:如果T中一个结点x的右子树为空,且x有一个后继y,那么y一定是x的最底层祖先,并且其左孩子也是x的祖先。(注意到,每个结点都是它自己的祖先。)文心一言,代码正常运行:灵捷3.5。为了证明上述命题,我们需要定义几个......
  • 文心一言 VS 讯飞星火 VS chatgpt (150)-- 算法导论12.2 6题
    六、用go语言,考虑一棵二叉搜索树T,其关键字互不相同。证明:如果T中一个结点x的右子树为空,且x有一个后继y,那么y一定是x的最底层祖先,并且其左孩子也是x的祖先。(注意到,每个结点都是它自己的祖先。)文心一言,代码正常运行:灵捷3.5。为了证明上述命题,我们需要定义几个辅助......
  • 算法入门经典 刘汝佳 4.2 地址与指针
    4.2 地址和指针4.1节介绍的数学函数的特点是:做计算,然后返回一个值。有时候,我们要做的事情 并不是“计算”——如交换两个变量;而有时候,我们需要返回两个甚至更多的值——如解一个二元一次方程组。4.2.1 变量交换程序4-4 用函数交换变量(错误)#include<stdio.h>void swap(in......
  • java基于权重的抽奖算法
    最近需要写一个抽奖的功能(附带权重),根据这位博主https://blog.51cto.com/u_16213431/7116970,的算法理解了一下,记录下来importjava.util.ArrayList;importjava.util.List;importjava.util.Random;publicclassHelloWorld{publicstaticvoidmain(String[]args){......
  • 不平衡少样本数据集的算法方案
    在图像实际的细分场景中,经常会遇到数据集不均衡以及数据集数量有限等问题,如何有效利用数据集,提升自己的算法效果,这里大刀基于自己的实际项目经验,分享在实际图像分类领域遇到问题,以及解决的方案,供参考。前言大家好,我是张大刀。之前有个智慧工地的项目,其中一个需求是监控工地......
  • 基于PLE结合卡尔曼滤波的RSSI定位算法matlab仿真
    1.算法运行效果图预览     2.算法运行软件版本MATLAB2022a 3.算法理论概述        基于PLE(Power-LawEqualizer)结合卡尔曼滤波的RSSI(ReceivedSignalStrengthIndicator)定位算法是一种利用无线信号强度进行位置估计的方法。该方法通过PLE算法对RSSI......
  • 算法~布隆过滤器
    布隆过滤器(BloomFilter)是一种高效的概率数据结构,用于判断一个元素是否存在于集合中。它基于位数组和多个哈希函数,并具有以下特点:BloomFilter是一个基于概率的数据结构:它只能告诉我们一个元素绝对不在集合内或可能在集合内快速查询:布隆过滤器具有快速查询的特性。它使用多......
  • AES java加密与MySql加密算法一致
    1.背景数据库加密与java程序加密算法保持一致,统一采用AES加密算法。2.java代码加密1packagecom.pacific.permission.test;23importjavax.crypto.Cipher;4importjavax.crypto.spec.SecretKeySpec;5importjava.util.Base64;67/**8*@authorluzhi......