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

喜欢ヅ旅行 2022-08-28 01:46 167阅读 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 条评论，167人围观）

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

相关阅读

相关单调栈专题

问题驱动型分析博客： 1. 题目是这样的，给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自

青旅半醒/ 2023年08月17日 15:14/ 0 赞/ 64 阅读

相关单调栈

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

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

相关 AcWing 830. 单调栈

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

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

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

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

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

相关单调栈的简单应用

栈是一种先进后出的数据结构，只能在栈顶进行元素的入栈和出栈，栈可以使用数组或者是链表进行实现，栈只提供几个受限的操作。 ![watermark_type_ZHJvaWRzYW

青旅半醒/ 2022年09月12日 08:57/ 0 赞/ 152 阅读

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

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

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

相关单调栈

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

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

相关单调栈学习

学习可参考如下博客： [单调栈原理及应用详解附各种类型的题目练习][Link 1] 视频学习：[【算法讲堂】【电子科技大学】【ACM】单调队列与单调栈][ACM] 单

ゞ浴缸里的玫瑰/ 2022年02月22日 03:02/ 0 赞/ 218 阅读

相关单调栈

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

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

相关单调栈

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

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