单调栈（Monotonic Stack）是算法中一种非常实用的数据结构技巧，核心思想是维护一个栈，使得栈中元素始终保持单调递增或单调递减的顺序。它常用于高效解决“下一个更大/更小元素”类问题，时间复杂度通常为 O(n)。

什么是单调栈？

从栈底到栈顶都是单调变化的元素，单调变化指的是单调(非)递增/减(包含相等的情况)。
递增用于解决寻找第一个更小的元素，递减反之。

为什么用单调栈？

通常遇到需要数组中两个元素进行比较，找到下一个更大或者更小的元素这类问题的时候，遍历两边能够得到答案，因为每个元素至少需要与其他元素进行比较后才知道谁是大小王！ O(n^2)的复杂度。
那么对于要求下一个更大的元素是什么的时候呢？乍一看，每个元素只需要与后面的元素进行比较就行了，但是复杂度也是O(n^2)，但是如果我们使用单调栈来做的话，时间复杂度就可以降低到O(n)了。
为什么可以降低到O(n) 呢？因为在单调栈方法下，每个元素只会遍历一次，而且每个元素也最多只会入栈一次、出栈一次，那综合下来也就是只有O(n)了。

用简单的逻辑来描述就是：
背景：求下一个更大元素
0. 每个元素A都与队伍最后一个元素B进行比较

  1. 如果队伍是空的，A去排队，然后让下一个元素来；
  2. 如果B比A小，让B元素记住A，然后B退出当前队伍，因为他已经得到他的目标元素了；
  3. 如果B元素比A大，去一边排队；
  4. 最后队伍里剩下一个没有比他更大的元素，让他记住0（或者是自己）

用人话来说：
背景：教室里面的学生随意排队比较身高，让每个学生记住他后面第一个比自己高的学生。
0. 第一个学生出来后站旁边排队

  1. 下一个学生出来和排队的学生比身高
    1. 如果新出来的比排队的第一个人高，让排队的第一个人记住新出来的人的名字，然后离开，其他排队的同学向前一步走，队伍最前面的人继续比身高
    2. 直到队伍最前面的人比新出来的人高，这时候让新出来的人去队伍最前面排队，然后教室里出来下一个学生
  2. 最后队伍剩下一个人，让他记住自己好了。

场景1

寻找每个元素右边第一个比它大的元素（Next Greater Element）

  • 暴力求解
1
2
3
4
5
for i in range(n):
    for j in range(i+1, n):
        if a[j] > a[i]:
            result[i] = a[j]
            break
  • 单调栈求解
1
2
3
4
5
6
stack = []
for i in range(n):
    while stack and a[i] > a[stack[-1]]:
        idx = stack.pop()
        result[idx] = a[i]
    stack.append(i)

场景2

leetcode题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：
    1 <= temperatures.length <= 105
    30 <= temperatures[i] <= 100

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res(temperatures.size(), 0);
        stack<int> st;

        for(int i = 0; i < temperatures.size(); i++)
        {
            while(!st.empty() && temperatures[i] > temperatures[st.top()])
            {
                auto index = st.top(); st.pop();
                res[index] = i - index;
            }
            st.push(i);
        }
        return res;
    }
};

场景3

柱状图中最大的矩形
实现代码：

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
29
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int res = 0;
        int length = heights.size();

        for(int i = 0; i < length; i++)
        {
            while(!st.empty() && heights[i] < heights[st.top()])
            {
                int index_of_high = st.top(); st.pop();
                int left = st.empty() ? -1 : st.top();
                res = std::max(res, (i - left -1)*heights[index_of_high]);
            }
            st.push(i);
        }

        // 处理剩余的单调元素 1,2,3  index 1,4,5
        while(!st.empty())
        {
            int now = st.top(); 
            st.pop();
            int before = st.empty() ? -1 : st.top();
            res = std::max(res, heights[now] * (length - before - 1));
        }
        return res;
    }
};

这个题目的暴力求解就是获取每个元素在队列中比他小的左边界和右边界，然后再遍历求出每个矩形的大小。

上一种解法最后会剩下一个单调的元素序列需要进行额外一次迭代处理，那如果扩充一下原来的数据添加两个小于所有元素的元素进去，也就是说会打断元素们构建矩形的元素(0)，这样最后就不会有剩余的单调元素了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

stack<int> st;
vector<int> expanded_heights(heights.size()+2, 0);
// std::copy(heights.begin(), heights.end(), expanded_heights.begin()+1);
std::memcpy(expanded_heights.data()+1, heights.data(), sizeof(int)*heights.size());
// for(int i = 1; i <= heights.size(); i++) expanded_heights[i] = heights[i-1];
int res =0;
for(int i = 0; i < expanded_heights.size(); i++)
{
	while(!st.empty() && expanded_heights[i] < expanded_heights[st.top()])
	{
		int index = st.top();
		st.pop();
		int left_index = st.empty() ? -1 : st.top();
		res = std::max(res, (i - left_index -1) * expanded_heights[index]);
	}
	st.push(i);
}
return res;

场景4

最大矩形
在二维矩阵中找只包含1的最大矩形，可以通过一定的分析发现，这其实就是在场景3的基础上额外多增加了一维的遍历，如下图所示。

这样来理解代码就非常容易理解了，在场景3的代码外面加一个将当前矩阵处理为右侧直方图的步骤即可，然后循环内容调用场景3的代码来完成。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int res = 0;
        int length = heights.size();

        for(int i = 0; i < length; i++)
        {
            while(!st.empty() && heights[i] < heights[st.top()])
            {
                int index_of_high = st.top(); st.pop();
                int left = st.empty() ? -1 : st.top();
                res = std::max(res, (i - left -1)*heights[index_of_high]);
            }
            st.push(i);
        }

        // 处理剩余的单调元素 1,2,3  index 1,4,5
        while(!st.empty())
        {
            int now = st.top(); 
            st.pop();
            int before = st.empty() ? -1 : st.top();
            res = std::max(res, heights[now] * (length - before - 1));
        }
        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        vector<int> raw(matrix[0].size(), 0);

        int res = 0;
        for(int i = 0; i < matrix.size(); i++)
        {
            for(int j = 0; j < raw.size(); j++)
            {
                int num = matrix[i][j] - '0';
                raw[j] = num == 0 ? 0 : raw[j]+num;
            }

            res = std::max(res, largestRectangleArea(raw));
        }
        return res;
    }
};
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Share