首页 > 其他分享 >单调栈

单调栈

时间:2024-04-03 15:12:35浏览次数:23  
标签:int big tt stk -- 单调

依据

单调栈具有贼有趣的实现方式:
在查找的同时,删除多余的,插入新的
那么删除插入的过程和依据呢?

我是nums[i],以找出左边第一个比我小的元素为例:
栈里的元素是非降序的,而且都在我左边
凡是栈里比我大的数(记为big),对找出左边第一个比我小的数来说,无效,可删
对我右边的数来说,big也是对他们无效的(对他们来说我更近,还比big更小),也可删
执行删除
找到比我小的数记为small,可以把small这样那样做若干处理
我的左边第一个比我小的元素找好了,我加入栈顶

轮到nums里下一个开始找,从栈顶开始,凡是比他大的数,可删...

以下是acwing 830. 单调栈

模板1-数组存储后再遍历

#include <iostream>
using namespace std;

const int N = 100050;
int a[N],q[N];

int main(){
    int n,tt=0;
    cin>>n;
    for(int i=0;i<n;i++ ){
        cin>>a[i];
}
    for(int i=0;i<n;i++ ){
        while(tt>0 && q[tt]>=a[i]) tt--;
        if(tt==0) cout<<"-1"<<" ";
        else cout<<q[tt]<<" ";
        q[++tt]=a[i];
    }
        return 0;

模板2-单变量读入不存储

#include <iostream>
using namespace std;

const int N = 100010;
int stk[N], tt;

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

标签:int,big,tt,stk,--,单调
From: https://www.cnblogs.com/aijisjtu/p/18112726

相关文章

  • QMIX:用于深度多智能体强化学习的单调值函数分解
    目录QMIX:MonotonicValueFunctionFactorisationfor DeepMulti-AgentReinforcementLearningQMIX:用于深度多智能体强化学习的单调值函数分解Abstract 摘要1Introduction引言2RelatedWork 2相关工作3Background 3背景 3.1Deep Q-Learning 3.1深......
  • 蓝桥杯算法集训 - Week 4:BFS、并查集、Flood Fill、哈希、单调栈/队列
    蓝桥杯算法集训-Week4本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、BFSBFS算法复习参考:BFS(Java)广度优先搜索简单介绍、模板、案例(一)Ⅰ、代码模板staticvoidbfs(Troot){//双端队列,用来存储元素D......
  • 【模板】单调队列 滑动窗口最值
    LuoguP1886滑动队列/单调队列有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 以求最小值为例f[i]表示以i结尾的窗口中的最小值f[i]=min(a[j]),i-k+1<=j<=i暴力算法O(n^2)......
  • 单调栈的妙用
    单调栈的妙用题目1题目链接402.移掉K位数字-力扣(LeetCode)题目大意给你一个以字符串表示的非负整数num和一个整数k,移除这个数中的k位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。示例输入:num="1432219",k=3输出:"1219"解释:移除掉三个数......
  • 单调队列 维护区间最值(板子+两道练手)
    1.P1886滑动窗口/【模板】单调队列https://www.luogu.com.cn/problem/P1886板子题,传送门在上方//Problem://P1886滑动窗口/【模板】单调队列////Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1886//MemoryLimit:500MB//TimeLimit:1......
  • 数据结构(三)单调栈---以题为例
    给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。输入格式第一行包含整数 N,表示数列长度。第二行包含 N 个整数,表示整数数列。输出格式共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出......
  • 【每日算法】常见AIGC模型; 刷题:力扣单调栈
    上期文章【每日算法】理论:生成模型基础;刷题:力扣单调栈文章目录上期文章一、上期问题二、理论问题1、stablediffusion模型的网络架构2、T5的网络架构(Text-To-TextTransferTransformer模型)3、SDXL模型4、DALLE5、BPE编码6、为什么DDPM加噪声的幅度是不一致的?三、力......
  • 代码随想录算法训练营第六十天 | 单调栈 柱状图中最大的矩形 完结撒花
    目录柱状图中最大的矩形LeetCode84.柱状图中最大的矩形柱状图中最大的矩形双指针解法本题要记录记录每个柱子左边第一个小于该柱子的下标,而不是左边第一个小于该柱子的高度。在寻找的过程中使用了whileclassSolution{publicintlargestRectangleArea(in......
  • 单调队列
    题目1点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definepiipair<int,int>#defineinf0x3f3f3f3fsignedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intn,m;cin>>n>>m;......
  • 单调栈C++
    一、每日温度  1、题目:请根据每日气温列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用0来代替。例如,给定一个列表temperatures=[73,74,75,71,69,72,76,73],你的输出应该是[1,1,......