LeetCode 刷题

何为单调栈？顾名思义，单调栈即满足单调性的栈结构，可以是单调递增或单调递减。在单调栈中，栈顶元素是栈内最大（或最小）的元素，而栈底元素是栈内最小（或最大）的元素。

单调栈在解决一些与区间相关的问题时非常有用 。它可以帮助我们快速找到每个元素左边或右边第一个比它大或小的元素：通过维护一个单调递增栈，我们可以找到每个元素右边第一个比它小的元素；通过维护一个单调递减栈，我们可以找到每个元素右边第一个比它大的元素。

单调栈

单调栈（monotonic stack）是一种特殊的栈数据结构，常用于解决与区间相关的问题。它的特点是栈内元素具有单调性，可以是单调递增或单调递减。

这里的「单调」为广义上的单调，即为非严格单调性，包括「等于」的情况。

基本操作

单调栈支持以下操作：

• 入栈（push）：将元素压入栈顶。
• 出栈（pop）：将栈顶元素弹出。
• 获取栈顶元素（top）：返回栈顶元素的值，但不弹出栈顶元素。
• 判断栈是否为空（isEmpty）：返回栈是否为空的布尔值。

应用场景

单调栈在解决一些与区间相关的问题时非常有用 ，例如：

• 寻找每个元素右边第一个比它大（或小）的元素。
• 寻找数组中的下一个更大（或更小）元素。
• 寻找数组中的最大矩形面积（矩阵是以数组中的值为高度、宽度指定）。

算法思想

单调栈的基本思想是维护一个单调递增或单调递减的栈。具体操作如下：

• 对于每个元素，如果栈为空或当前元素大于（或小于）栈顶元素，则将当前元素入栈。
• 如果当前元素小于（或大于）栈顶元素，说明找到了栈顶元素的右边第一个小于（或大于）它的元素。此时，可以对栈进行出栈操作，直到栈为空或新元素大于（或小于）栈顶元素。
• 继续将当前元素入栈。

维护单调栈示例过程

对于数组 [2,1,5,6,2,3]，我们维护一个单调递增栈（栈底元素最小、栈顶元素最大）的过程如下：

第一步，栈为空，入栈新元素 2，此时单调递增栈（左侧为栈底、右侧为栈顶）的状态为：

1

monoStack: [2]

第二步，栈不为空，新元素 1 小于栈顶元素 2，弹出元素 2 后，栈为空，入栈新元素 1：

1

monoStack: [1]

第三步，栈不为空，新元素 5 大于栈顶元素 1，入栈新元素 5；栈不为空，新元素 6 大于栈顶元素 5，入栈新元素 6：

1

monoStack: [1, 5, 6]

第四步，栈不为空，新元素 2 小于栈顶元素 6，栈顶元素 6 出栈；栈不为空，新元素 2 小于栈顶元素 5，栈顶元素 5 出栈：

1

monoStack: [1]

第五步，栈不为空，新元素 2 大于栈顶元素 1，新元素入栈后满足单调性，新元素 2 入栈：

1

monoStack: [1, 2]

第六步，栈不为空，新元素 3 大于栈顶元素 2，新元素入栈后满足单调性，新元素 3 入栈：

1

monoStack: [1, 2, 3]

由第二步可知，元素 2 右侧第一个比它小的元素是元素 1；由第四步可知，元素 5 和元素 6 右侧第一个比它小的元素都是元素 2；由最后一步可知，元素 1,2,3 右侧没有比它小的元素。

伪代码

单调递增栈

单调递增栈的栈顶元素最大，新插入的元素要不小于栈顶元素，否则只能把栈顶元素一个一个地弹出栈，直到满足为止。

1
2
3
4
5

// insert x
while (!monoStack.empty() && x < monoStack.top()) {
    monoStack.pop()
}
monoStack.push(x)

单调递减栈

单调递减栈的栈顶元素最小，新插入的元素要不大于栈顶元素，否则只能把栈顶元素一个一个地弹出栈，直到满足为止。

1
2
3
4
5

// insert x
while (!monoStack.empty() && x > monoStack.top()) {
    monoStack.pop()
}
monoStack.push(x)

复杂度

每个元素最多只会进栈、出栈一次，故时间复杂度为 O(n)，空间复杂度为 O(n)，n 为元素数量。

单调栈应用场景实现

题目：寻找数组中每个元素右边比它小的第一个元素。

实现代码

这可以使用单调递增栈找到每个元素右边第一个比它小的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>
#include <string.h>

void findNextSmaller(int nums[], int n, int res[]) {
    int monoStack[n], size = 0; // 使用数组模拟栈结构 

    for (int i = 0; i < n; i++) {
        res[i] = -1; // 初始化结果数组，-1 表示右侧没有比我小的元素 

        while (size > 0 && nums[i] < nums[monoStack[size - 1]]) {  // monoStack.top()
            res[monoStack[--size]] = nums[i];  // monoStack.pop()
        }
        monoStack[size++] = i;  // monoStack.push(x)
    }
}

int main(int argc, char *argv[]) {
    int nums[] = {2, 1, 5, 6, 2, 3};
    int n = sizeof(nums) / sizeof(nums[0]);
    int res[n];

    findNextSmaller(nums, n, res);
    for (int i = 0; i < n; i++) {
        printf("%d next smaller: %d\n", nums[i], res[i]);
    }

    return 0;
}

测试结果

1
2
3
4
5
6

2 next smaller: 1
1 next smaller: -1
5 next smaller: 2
6 next smaller: 2
2 next smaller: -1
3 next smaller: -1

这个结果与上面的“维护单调栈示例过程”中的举例的结果一致。

代码分析

在代码实现中，我们并没有直接在单调栈 monoStack 中存储数组元素的值，而是存储了数组元素对应的索引：

1. 这方便了通过索引向结果数组 res 的对应位置，填充右边第一个比它小的值；
2. 因为原始数组 nums 的索引对应的值不会改变，我们依然可以通过 monoStack 中维护的索引，获取对应的值，保证栈的单调性。