Comment on page

Monotonous Stack

Monotonous stack

单调栈(单调队列)

△ 单调递减栈:A[i] >= A[stack.top()]
▽ 单调递增栈:A[i] <= A[stack.top()]
单调栈是一种维护栈内元素递增(或递减)的栈。
单调栈分为单调递增栈和单调递减栈,单调递增栈即栈内元素保持单调递增的栈,同理单调递减栈即栈内元素保持单调递减的栈。
单调栈里可以保存元素的值或下标
某些场景下,我们需要维护栈底,这时候栈的数据结构是不满足要求的,可能需要借助队列双端队列实现(比如求滑动窗口最大值),即单调队列

应用场景

  • 可以在O(N)的时间复杂度,找出每个数左右两边第一个大于或小于它的解
  • 单调递增栈用于查找两边第一个小于当前元素的值,单调递减栈用于查找两边第一个大于当前元素的值
  • 一般数组中的单调性问题,题目中隐含第一个或离此元素最近的大于或小于元素的值,这类问题都可以考虑下,用单调栈是否可以求解

动画演示

数列7 4 9 5 3 2构建单调递减栈
单调栈动画演示

代码模板

stack<int> stk;
for (int i = 0; i < A.size(); i++) {
while (stk.size() && A[i] <= A[stk.top()]) { // 单调递增栈(
// 单调递减栈A[i] >= A[stk.top()]
stk.pop();
}
stk.push(i);
}

板子题

给定一个长度为N的正整数数组,输出每个数左右两边第一个比它小的数,如果不存在则输出-1。
输入: [3, 4, 2, 7, 5]
输出:
左边:[-1, 3, -1, 2, 2]
右边:[2, 2, -1, 5, -1]

解题思路

查找左右两边第一个更小的元素,使用单调递增栈
  • 入栈时,当前元素左边的第一个更小的元素当前栈顶元素
  • 出栈时,栈顶右边第一个更小的元素即将入栈的当前元素

代码实现

void sumSubarrayMins(vector<int> &A) {
int n = A.size();
vector<int> lmin(n, -1);
vector<int> rmin(n, -1);
stack<int> stk; // 单调递增栈
for (int i = 0; i < A.size(); i++) {
while (stk.size() && A[i] <= A[stk.top()]) {
rmin[stk.top()] = A[i];
stk.pop();
if (stk.size()) lmin[i] = A[stk.top()];
}
stk.push(i);
}
}
时间复杂度O(N),空间复杂度O(N)

题目

全局单调栈

上面我们遇到的单调栈问题,都是维护的连续性的局部子序列的单调性,还有一类问题,需要求解全局性的单调性序列,