---
title: "单调栈"
created: 2025-11-28
tags:
  - 算法
---

# 单调栈

## 题目 [单调栈](https://www.acwing.com/problem/content/832/)

![[image-1bcadaf0.png]]

## 思路分析

用的地方很少 其实可以归纳进双指针问题 是对双指针问题暴力后的一个改进

比如 在序列中 要求每个数左边的最近的比它小的数

3 4 2 7 9

-1 3 -1 2 7

乍一看是双指针问题 暴力过一遍

i从0~n

j从i-1~0

找小于a[i]的数

break

接下来就是找特点 寻求优化

i往右走的过程中 可以使用栈去存放左边的所有元素

那这就有优化空间了

怎么减少栈里面没用的数据 从而减少出栈的次数

分析一下

3 4 2 7

如果在7这个位置 前面的3 4 2应该都是满足小于7的

但是取到的只有2 因为最近

那意思就是说 在7这里 栈里面完全可以只有2

3 4 2 7 9

9这里 可不可以栈中只有7？

3 4 2 7 4

显然不能 如果换成一个小于7的数 真正的结果2就丢失了

可以发现 若存在 x=ay的情况

则可以把ax剔除掉

ay永远是较与ax的最优解 ax存不存在就没关系了（ay在一天 ax就永无出头之日）

画成图就是说 栈中只要存在这种往下的线段 就去掉

最后得到的栈里面的元素一定是单调的

且栈顶一定就是要求的值 要么就是空 没有符合要求的值

其实就是一个变插入边判断删除的过程 确保栈内都是答案

这样每个元素都最多只会进栈出栈一次 相较于原本的每次都前面所有数入栈再逐个出栈找

要优化了很多

然后原本的数组都可以不用另外存储了 反正下一个数的答案要么就是栈顶要么就是栈空没有 直接依次对各个数进行判断 对单调栈进行调整

//栈里有元素 且当前元素进入后会产生逆序 就删掉那些没有出头日的元素

`while(tt && stk[tt]>=x)`

`tt--;`

`if(!tt)`

`printf(“-1 “);//栈空的话 说明没有答案`

`else`

`printf(“%d “,stk[tt]);//否则栈顶元素就是答案`

`stk[++tt]=x;//把该元素入栈`

![[image-150c5552.png]]

![[image-56889add.gif]]

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int stk[N];
int 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;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/02-听课板子/数据结构/栈与队列/队列|队列]] 🏠 [[00-听课板子]] ➡️ [[2-Learning/02-算法/02-听课板子/数据结构/栈与队列/单调队列|单调队列]]