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

# 单调栈

## 单调栈 找最近

**用于找每个数 左/右边 最近的 比它小/大 的数**

### **(1)左边 最近的 小于它 的数**

从1~n遍历

序列应该是单调递增（保证栈头为最优解）

所以如果出现向下趋势 就不断出栈

```cpp
while(tt && x <= stk[tt])
    tt--;
//具体操作
//…… //把栈头作为答案保存
stk[++tt]=x;//把该元素入栈
```

![[image-150c5552.png]]

### **(2)左边 最近的 大于它 的数**

从1~n遍历

序列应该是单调递减

所以如果出现向上趋势 就不断出栈

```cpp
while(tt && x >= stk[tt])
    tt--;
//具体操作
//…… //把栈头作为答案保存
stk[++tt]=x;//把该元素入栈
```

### **(3)右边 最近的 小于它 的数**

从n~1遍历

序列应该是单调递增

所以如果出现向下趋势 就不断出栈

```cpp
for(int i=n;i>=1;i--){
    while(tt && h[i] <= h[stk[tt]])
      tt--;
    //具体操作
    //…… //把栈头作为答案保存
    stk[++tt]=i;//把该下标入栈
}
```

### **(4)右边 最近的 大于它 的数**

从n~1遍历

序列应该是单调递减

所以如果出现向上趋势 就不断出栈

```cpp
for(int i=n;i>=1;i--){
    while(tt && h[i] >= h[stk[tt]])
      tt--;
    //具体操作
    //…… //把栈头作为答案保存
    stk[++tt]=i;//把该下标入栈
}
```

想清楚要找什么

考虑遍历方向

和答案应该是较大的还是较小的

较小的话 栈里应该是单调递增 这样才能保证栈顶是最合适的答案

较大的话 反过来 栈里应该是单调递减

## 单调栈+二分 找最远

### (1)左边 最远的 大于它 的数

比如 对于3来说 如果左边已经有了5 在53中间再来一个4是完全没有必要的 因为3肯定找到的是那个5 因为更大 且更远 由此发现是一个不出现递减趋势的序列

但个53中间有个7的话 这个7虽然不会被3找到 但是它可能会被后面的一个6找到

综上 构造一个单调递增的序列

若这个新加的数能保持递增趋势 说明不存在比它更大的数 没必要去找了 直接加进去 供后面的数去找

如果不能保持递增趋势 就说明左边有一个比它更大的数 在这个已有的单调序列中二分找到

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

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    //需要注意的一点是 stk存的是下标
    for(int i=1;i<=n;i++){
    	//a[i]>a[stk.back()] 还是 a[i]>=a[stk.back()]
        //加不加等号看题意
        //找严格小于它的数的话 这里加等号 意味着找到它自己
        //找前面小于等于它的数的话 这里不加等号
		if(stk.empty() || a[i]>=a[stk.back()]){//发现该元素比栈顶元素还大（保持单调递增）
            stk.push_back(i);//直接入栈
            ans[i]=i;//记录答案 可能求长度等等
        }
        else{//发现该元素不是最大  那么原单调序列里肯定存在一些比他大的数 二分找到最远的那个
            int l=1,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]>a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}
```

### (2)左边 最远的 小于它的数

同理 现在找最小的数 如果本身已经是最小了 就没必要找 直接加入单调栈保持单调性 如果自身不是最小 也不做什么踢出操作 直接在单调栈里找答案就行
只不过它也没必要加进去

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

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<=n;i++){
        if(stk.empty() || a[i]<a[stk.back()]){//只要改两处
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]<a[i]) //只要改两处
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}
```

### (3)右边 最远的 大于它的数

从右边开始枚举罢了 1-n变成n-1即可

找最远的大于 若该数是最大的 直接加入栈中 如果不是 再二分找一下

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

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=n;i>=1;i--){//只需改循环
        if(stk.empty() || a[i]>a[stk.back()]){
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]>a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}
```

### (4)右边 最远的 小于它的数

n-1 最小 若该数为最小 直接加入 否则 二分找

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

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=n;i>=1;i--){
        if(stk.empty() || a[i]<a[stk.back()]){
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]<a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}
```

总结

**思路上：**

![[image-48de97e5.png]]

**代码上：**

一个是以当前元素维护单调栈 不断剔除里面元素使其保持单调性

一个是判断当前元素是否符合单调栈的特性 符合就加入 不符合可以直接在栈里找答案

## 题目

- [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调栈/单调栈|单调栈]]
- [[仰视奶牛|仰视奶牛]]
- [[发射站|发射站]]

- [[直方图中最大的矩形|直方图中最大的矩形]]
- [[最大矩形|最大矩形]]
- [[城市游戏|城市游戏]]

- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/最长连续子序列|最长连续子序列]]

- [[2-Learning/02-算法/03-刷题理模型/双指针相关模型/对撞指针/接雨水|接雨水]]

**更多题目：**

- [包含min函数的栈](https://www.acwing.com/problem/content/90/)
- [矩形牛棚](https://www.acwing.com/problem/content/1415/)
- [最大面积](https://www.acwing.com/problem/content/description/3519/)
- [最小栈](https://leetcode-cn.com/problems/min-stack/)
- [栈的最小值](https://leetcode-cn.com/problems/min-stack-lcci/)
- [剑指 Offer II 038. 每日温度](https://leetcode-cn.com/problems/iIQa4I/)
- [用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/)
- [剑指 Offer 09. 用两个栈实现队列](http://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)
- [化栈为队](https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci/)
- [最后 K 个数的乘积](http://leetcode-cn.com/problems/product-of-the-last-k-numbers/)
- [去除重复字母](https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/)
- [不同字符的最小子序列](http://leetcode-cn.com/problems/product-of-the-last-k-numbers/)
- [柱状图中最大的矩形](http://leetcode-cn.com/problems/largest-rectangle-in-histogram/)
- [剑指 Offer II 039. 直方图最大矩形面积](https://leetcode-cn.com/problems/0ynMMM/)
- [最大矩形](http://leetcode-cn.com/problems/maximal-rectangle/)
- [剑指 Offer II 040. 矩阵中最大的矩形](http://leetcode-cn.com/problems/PLYXKQ/)
- [接雨水](http://leetcode-cn.com/problems/trapping-rain-water/)
- [直方图的水量](https://leetcode-cn.com/problems/volume-of-histogram-lcci/)
- [最大子矩阵](https://leetcode-cn.com/problems/max-submatrix-lcci/)

---
⬅️ [[链表相关问题|链表相关问题]] 🏠 [[00-刷题理模型]] ➡️ [[仰视奶牛|仰视奶牛]]