首页 > 其他分享 >单调栈

单调栈

时间:2022-11-21 12:26:03浏览次数:53  
标签:top pop st push id 单调

title: 单调栈
date: 2022-11-17 20:33:16
tags: 算法

本文章遵守知识共享协议 CC-BY-NC-SA ,转载时需要署名,推荐在我的个人博客阅读。

单调栈是一种可以在线性时间中计算出一个序列中 大于/小于 任意一个左/右元素的值。

前置知识

讲解

单调栈,顾名思义,就是内部元素保持单调的栈。

对于维护,我们只需要在加入时先判断

for(int i=1;i<=n;i++){
    scanf("%d",&tmp);
    while(!st.empty() && tmp > st.top()){
        flg[id.top()] = i; // 标记
        st.pop(); // 弹出
        id.pop(); // 弹出
    }
    id.push(i);
    st.push(tmp);
}
flg[id.top()] = 0;

例题

P5788-【模板】单调栈

模板题目,直接做。

标签:top,pop,st,push,id,单调
From: https://www.cnblogs.com/rickyxrc/p/16911026.html

相关文章

  • 单调队列优化DP
    先存这里理解了再继续编写CF1077F2PictureswithKittens(hardversion)#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllN=5e3+10......
  • 垃圾收集器使用场景和ZGC的简单调优
    本文背景在对于去哪儿网的《ZGC在去哪儿机票运价系统实践》的这篇文章阅读之后,对于parNew+cms这对垃圾收集的组合和g1以及zgc这几种垃圾收集器有了更加深入的了解,特此形......
  • 单调栈/单调队列
    单调栈/单调队列典型力扣题目239:滑动窗口最大值双端队列,队列存放元素按一定规则有序//双端队列Deque:LinkedList,ArrayDeque,LinkedDeque,LinkedBlockingDequeDequ......
  • 单调队列优化DP
    [POI2015]WIL题目描述给定一个长度为\(n\)的序列,你有一次机会选中一段连续的长度不超过\(d\)的区间,将里面所有数字全部修改为\(0\)。请找到最长的一段连续区间,使得......
  • 使用单调队列解决 “滑动窗口最大值” 问题
    1\.单调队列的典型问题单调队列是一种用来高效地解决“滑动窗口最大值”问题的数据结构。举个例子,给定一个整数数组,要求输出数组中大小为K的窗口中的最大值,这就是窗口......
  • 单调栈&单调队列
    单调栈&单调队列&尺取PassingtheMessageHDU3410题意:给定n个数,找每一个数左边比它小的最大的数,右边比它小的最大的数,每个数不能越过一个比它大数数去找后面的数。解......
  • C++——单调队列
    classSolution{public:classMyqueue//单调队列{public:deque<int>que;//因为只维护了队列最大值,故在pop时判断滑动窗口最......
  • 道长的算法笔记:单调栈查找前驱与后继
    单调栈单调栈是一种满足单调性的栈结构,其维护单调性方式是弹出栈顶不符合的条件的元素,也就是说,单调栈存储的并非入栈的全部元素,相当一部分元素会被弹掉。使用单调栈通常......
  • JS/TS数据结构---栈(单调栈)和队列
    一、栈栈(stack)是一种操作受限的线性表数据结构,基于后进先出(LIFO)策略的集合类型,例如函数中的临时变量符合后进先出的特性,因此用栈保存最合适。  在入栈和出栈过程中所需......
  • 【XSY3535】购物(决策单调性优化DP,分治,结论,背包)
    题面购物题解决策单调性全忘了……先考虑暴力怎么做,我们可以设\(f_{i,j}\)表示前\(i\)个商店买了\(j\)件物品的最小代价,然后有转移:\[f_{i,j}=\min_{k=0}^j(f_{i......