[C++知识库]单调栈（附例题）

何为单调栈

顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例如，栈中自顶向下的元素为$1,3,5,10,30,50$，插入元素$20$时为了保证单调性需要依次弹出元素$1,3,5,10$，操作后栈变为$20,30,50$。

模板

stack<int>st;
while(!st.empty() && a[st.top()]<=a[i])
    st.pop();	//弹出栈顶元素 
ans[i] = st.empty()?0:st.top();	//栈顶就是答案
st.push(i);		//将当前坐标压入栈顶 

例题1

题目描述

给出项数为 n 的整数数列 $a_{1\dots n}$。

定义函数 $f(i)$代表数列中第 ii 个元素之后第一个大于 $a_i$的元素的下标，即 $f(i)={\min }_{i<j\le n,a_j>a_i}$。若不存在，则 $f(i)=0$。

试求出 $f(1\dots n)$。

输入格式

第一行一个正整数 $n$。

第二行 $n$个正整数 $a_{1\dots n}$。

输出格式

一行 $n$ 个整数 $f(1\dots n)$ 的值。

输入

5
1 4 2 3 5

输出

2 5 4 5 0

题目分析

从后往前扫，注意栈中存储的是值对应的坐标，对于每个点：首先弹出栈顶比她小的元素；此时栈顶就是答案；加入这个元素的坐标。

C++代码

#include<iostream>
#include<stack>
using namespace std;

#define max 100
int a[max], ans[max];
stack<int>st;

int main(){
	int n;
	cin >> n;
	for(int i=1; i<=n; i++)
		cin >> a[i];
	for(int i=n; i>=1; i--){
		while(!st.empty() && a[st.top()]<=a[i])
			st.pop();	//弹出栈顶元素 
		ans[i] = st.empty()?0:st.top();	//栈顶就是答案
		st.push(i);		//将当前坐标压入栈顶 
	}	
	for(int i=1; i<=n; i++)
		cout << ans[i] <<" ";
	return 0;
}

例题2

题目描述
给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最大的矩形区域里 1 的数量。

输入描述
第一行输入两个整数 n 和 m ，代表 n*m 的矩阵

接下来输入一个 n*m 的矩阵

输出描述
输出其中全是 1 的所有矩形区域中，最大的矩形区域里 1 的数量。

示例1
输入

1 4
1 1 1 0

输出

3

示例2
输入

3 4
1 0 1 1
1 1 1 1
1 1 1 0

输出

6

分析

依次遍历每一行，在第k行，统计从k,k-1……,，连续1的个数，记为weight。同时对于每一行依次求weight时，看作直方图，转换为单调栈问题

C++ 代码

#include<iostream>
#include <cstdio>
#include <algorithm>
#include<stack>
using namespace std;
const int N = 100010;

int n, m, MaxArea = 0, val;
int height[N];
stack<int>st;

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {	
        for (int j = 1; j <= m; j++) {
            scanf("%d", &val);
            height[j] = val ? height[j] + 1 : 0;	//遇到有0的height就归0 
        }
        for (int j = 1; j <= m; ++j) {
            //栈顶元素大 
            while(!st.empty() && height[st.top()] >= height[j]) {
            	int t = st.top();
				st.pop();
            	int left = st.empty() ? 0 : st.top();	//这一块面积左侧坐标，j是右侧坐标 
            	MaxArea = max(MaxArea, (j-left-1)*height[t]);
			}
			st.push(j);
        }
    }
    printf("%d\n", MaxArea);
    return 0;
}