单调栈 - AcWing 830. 单调栈（C++）- 简单

喜欢ヅ旅行 2022-08-28 01:46 336阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/832/][https_www.acwing.com_problem_content_description_832]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]

#include <iostream>
    #include <stack>
    #include <climits>
    using namespace std;
    const int N=INT_MAX;//包含在头文件<climits>中
    
    int main(){
        
        stack<int> stk;//=new stack<int>(N);
        int n,cnt;
    
        cin>>n;
        while(n--){
        
            int x;
            cin>>x;
            while(stk.size()&&x<=stk.top()) stk.pop();//如果栈不为空，且栈顶元素比当前元素的值大，则需pop()
            
            if(stk.empty()) cout<<"-1"<<" ";
            else cout<<stk.top()<<" ";
            
            stk.push(x);
        }
        cout<<endl;
        return 0;
    }

[https_www.acwing.com_problem_content_description_832]: https://www.acwing.com/problem/content/description/832/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3ab896b522a44bf8810e6d9d802bd397.png

发表评论取消回复

表情：

评论列表（有 0 条评论，336人围观）

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

相关阅读

相关单调栈

单调栈 -------------------- 1. 单调栈介绍 2. 求最大矩阵的大小 3. 烽火台 -------------------- 单调栈介

偏执的太偏执、/ 2023年06月22日 07:28/ 0 赞/ 61 阅读

相关单调栈

单调栈，设置一个数组a\[i\]，用一个栈存放该数组的下标，每次存放时先将所有大于等于a\[i\]的数弹出，最后再将i存入栈中，保证后续的所有的数都大于前面一个数，栈就是单调递

骑猪看日落/ 2023年02月26日 12:29/ 0 赞/ 26 阅读

相关单调栈

> 参考https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaru

叁歲伎倆/ 2022年12月12日 13:58/ 0 赞/ 270 阅读

相关 AcWing 600. 仰视奶牛（单调栈）

上一篇博客：[AcWing 830. 单调栈][AcWing 830.] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。

本是古典何须时尚/ 2022年10月27日 06:15/ 0 赞/ 86 阅读

相关 AcWing 830. 单调栈

上一篇博客：[AcWing 42. 栈的压入、弹出序列][AcWing 42.] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`f

末蓝、/ 2022年10月24日 13:24/ 0 赞/ 251 阅读

相关单调栈，栈还能单调一下？

之前遇到一个算法题目，自己只会用时间复杂度 O(N^2) 暴力解法解决，有大佬说用单调栈，可以做到 O(N) 的时间复杂度，当时我的表情是这样的： ![1d3f60a4338

水深无声/ 2022年09月12日 11:59/ 0 赞/ 285 阅读

相关单调栈 - AcWing 830. 单调栈（C++）- 简单

题目链接：[https://www.acwing.com/problem/content/description/832/][https_www.acwing.com_prob

喜欢ヅ旅行/ 2022年08月28日 01:46/ 0 赞/ 337 阅读

相关单调栈

通过使用栈这个简单的结构，我们可以巧妙地降低一些问题的时间复杂度。单调栈性质： 1、若是单调递增栈，则从栈顶到栈底的元素是严格递增的。若是单调递减栈，则从栈顶到栈底的元素

ゝ一纸荒年。/ 2022年05月12日 07:28/ 0 赞/ 348 阅读

相关单调栈

单调栈性质单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性，可能为单调递增，也可能为单调递减。模型例如下图就是一个单调递增的单调栈。 ![

你的名字/ 2021年11月10日 12:46/ 0 赞/ 388 阅读

相关单调栈

一、单调栈定义单调递增栈：数据出栈的序列为单调递增序列（比站内元素小就入栈，否则将栈中比当前元素小的元素弹出后再入栈）单调递减栈：数据出栈的序列为单调递减

水深无声/ 2021年09月21日 05:40/ 0 赞/ 513 阅读