单调栈（monotonous stack）

单调栈 (Monotonic Stack)

算法定义与核心性质

单调栈是一种基于普通栈（Stack）的变体数据结构。其核心特征在于：在元素不断压入与弹出的动态过程中，严格维护栈内元素呈现单调递增或单调递减的序列性质。
单调栈主要用于解决一维数组中寻找当前元素左侧或右侧第一个比其大（或小）的元素的问题。通过维护单调性，单调栈能够将嵌套循环的 $O(N^2)$ 暴力查找优化至全局 $O(N)$ 的时间复杂度。

分类与对应场景

通常情况下，单调栈内存储的是原数组的**索引（下标）**而非具体数值，以便于计算区间长度或距离。

• 单调递增栈（从栈底到栈顶元素单调递增）：用于寻找元素两侧第一个比当前元素小的位置。
• 单调递减栈（从栈底到栈顶元素单调递减）：用于寻找元素两侧第一个比当前元素大的位置。

复杂度分析

• 时间复杂度： $O(N)$。序列中的每个元素最多仅会入栈一次且出栈一次，整体时间代价与序列长度成正比。
• 空间复杂度： $O(N)$。最坏情况下（序列本身严格满足栈的单调性），所有元素均会被压入栈内。

状态转移与维护机制

以维护单调递减栈（寻找下一个更大元素）为例，设当前遍历到数组的第 $i$ 个元素 $A[i]$，栈为 $S$（存储索引），栈顶元素为 $S_{top}$。维护机制如下：

1. 若栈为空 或 $A[i]\le A[S_{top}]$：当前元素入栈不会破坏单调递减性质，直接将 $i$ 入栈（push）。
2. 若 $A[i]>A[S_{top}]$：当前元素入栈会破坏单调递减性质。此时，$A[i]$ 即为栈顶元素 $A[S_{top}]$ 右侧第一个更大的元素。
   • 记录 $S_{top}$ 的答案为 $A[i]$。
   • 将 $S_{top}$ 弹出（pop）。
   • 重复上述判定，直到栈为空或当前栈顶元素满足 $A[i]\le A[S_{top}]$ 时，再将 $i$ 入栈。

基础代码模板：寻找下一个更大元素

// 寻找右侧第一个比 A[i] 大的元素，返回其索引数组
vector<int> nextGreaterElement(const vector<int>& A) {
    int n = A.size();
    vector<int> res(n, -1); // 默认值为-1，表示未找到
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        // 当栈不为空，且当前元素大于栈顶元素对应的值时
        while (!st.empty() && A[i] > A[st.top()]) {
            int topIndex = st.top();
            st.pop();
            res[topIndex] = i; // 记录栈顶元素的答案为当前元素下标
        }
        st.push(i); // 当前元素索引入栈
    }
    return res;
}

例题

柱状图中最大的矩形

• leetcode84：柱状图中最大的矩形
• CSP00 C题：最大的矩形
  这类题需要找到所有元素的左侧和右侧首个更小的元素。
  使用递增或递减栈都可以解决。使用递增栈的核心遍历代码为：

vector<int> h(n+2);
h[0]=0;h[n+1]=0; // 把首尾置零就不需要特判边界条件。
for(int i=0;i<n+2;i++){
	while(!st.empty() && h[st.top()]>h[i]){
		int mid=st.top();
		st.pop();
		// 计算mid柱子对应的最大面积
		int width=i-st.top()-1,height=h[mid];
		// st.top() 是 mid 左边第一个比 h[mid] 矮的矩形条的下标。
		// i 就是 mid 右边第一个比它矮的矩形条的下标。
		ans=max(ans,(ll)width*height);
	}
	st.push(i);
}

总结

单调栈是一种空间与时间权衡下的极简数据结构。其实现逻辑在于遍历全集的过程中，通过维护序列局部数据的单调性，将全局极值查询等效转换为局部的入栈与出栈判定。在算法竞赛中，凡涉及“最近极值”、“最大扩展区间”、“次大值消除”等子问题，通常均可考虑应用单调栈进行常数级或线性级优化。

参考

单调栈
柱状图中最大的矩形