首页 > 其他分享 >单调栈

单调栈

时间:2022-11-30 22:12:31浏览次数:28  
标签:int cin st while include 单调 size

给定一个长度为 n 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

#include <iostream>
#include <stack>
using namespace std;
int n;
stack <int> st;

int main() {
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        while (st.size() && st.top() >= x) st.pop();
        if (st.size()) cout << st.top() << " ";
        else cout << "-1 ";
        
        st.push(x);
    }
    return 0;
}

  

标签:int,cin,st,while,include,单调,size
From: https://www.cnblogs.com/leetothemoon/p/16939914.html

相关文章

  • 《浅谈决策单调性动态规划的线性解法》阅读随笔
    读下来唯二的感想这就是集训队吗真nb这就是集训队吗写的什么jb这latex就很离谱好吧一个变量改好几次名字我都不知道他在干什么啊对了没实现代码啊都是找的st......
  • 单调栈和单调队列
    P5788【模板】单调栈入栈时候判定,如果不符合栈内的规则,则让栈顶的元素出栈。voidsolve(){stack<int>sc;ufr(i,1,n){if(sc.empty()){sc.emp......
  • 决策单调性优化dp二则
    CielandGondolas  CodeForces-321E题意:有n个人,第i个人和第j个人放在一起时会产生a[i][j]的沮丧值(是社恐吗),保证a[i][j]=a[j][i],两个人只产生一份沮丧值。将n个人分成......
  • 738.单调递增的数字 monotone-increasing-digits
    问题描述738.单调递增的数字解题思路将该数字的每一位数字变成数组dec<int>的一部分,然后依次遍历,直到dec[i]>dec[i+1],然后将dec[i+1]及以后的数字都变成9,如果dec[......
  • 单调栈
    title:单调栈date:2022-11-1720:33:16tags:算法本文章遵守知识共享协议CC-BY-NC-SA,转载时需要署名,推荐在我的个人博客阅读。单调栈是一种可以在线性时间中计算......
  • 单调队列优化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的窗口中的最大值,这就是窗口......