单调栈

单调栈:栈中从栈底到栈顶的数都是递增(减)的,为了维护这种结构在插入比当前栈顶大的数的时候都需要先将栈顶的数弹出,这样我们就能够知道弹出的这个数两边比它大的数了

下面使用Leetcode两道题举例:

84. Largest Rectangle in Histogram

题意

给定n个非负整数代表柱状图的条高,其中每个条的宽度为1,求柱状图中最大矩形的面积。

上面是一个柱状图,其中每个条形的宽度为1,给定高度=[2,1,5,6,2,3]。

最大的矩形显示在阴影区域,其面积为10个单位。
实例:

1
2
Input: [2,1,5,6,2,3]
Output: 10

思路
  • 如果height是升序的,例如:[1,2,3],那么就是比较(1 3)vs(2 2)vs(3 1),也就是max(height[i] (len(height) - 1))
  • 我们要找到最大的长方形面积,可以按照这种方式来找:对于数组中每个元素代表的高度,找到以当前这个高度为高的最大的长方形面积,那么遍历所有的高度即可。我们直接暴力求解的话,就是O(n^2)的复杂度。
  • 有了上述思路后,我们在遍历数组的时候维护一个栈,这个栈中的元素从底向上按照高度值递增。如果遇到当前bar的高度比栈顶元素低,那么就出栈直到栈顶元素低于当前bar的高度。关键就在这里,当我们将第i个元素弹出栈的时候,我们就可以计算以heights[i]为高的最大长方形的面积。在遍历完数组之后,栈内元素仍然需要继续弹出,最后所有元素都会依次出栈,意味着计算完了所有可能的最大面积,就可以得到结果了。
  • 再来分析一下这个算法的可行性:每一个元素都要入栈一次,出栈一次。入栈的时候的是遍历访问到它的时候,那出栈的时候意味着什么呢。在这里元素出栈意味着,我们已经计算了以它的高度为高的最大长方形面积。结合栈内元素的单调性,栈顶元素所对应的bar一定比出栈元素对应的bar小,所以以出栈元素对应的bar为高的长方形无法往左边延展。结合代码,我们已经判断过当前处理的第i个元素所对应的bar也比出栈元素对应的bar小,所以长方形无法往右边延展。这个元素和左右边界之间如果还有空隙,那么这些空隙里所存在的bar,一定是因为维护栈的单调性而被弹出了。也就是说,如果这些bar存在,那么一定比这个出栈元素所对应的bar高。既然这些bar的高度更高,那么就可以被纳入这个最大长方形面积的计算中,也就不影响当前出栈元素的最大长方形面积的计算。以上我们就证明了,当我们将第i个元素弹出栈的时候,我们计算了以heights[i]为高的最大长方形的面积。
  • 模拟一下过程:
    • 先加入一个0,方便最后可以全部弹栈出来。栈变成:[2,1,5,6,3,-1]
    • 2进栈,1比栈顶小,对2进行出栈,max_space = 2
    • 2被替换为1进栈,1继续进栈,这时栈为[1,1]
    • 5,6都是非降的,继续进栈,栈为[1,1,5,6]
    • 遇到3,是一个降序点;开始出栈,6出栈,对应space=61;5出栈对应space=52;下一个1比3小,不需要出栈。然后将5、6的弹栈后的空位压栈为3,这是栈为[1,1,3,3,3]
    • 下一步遇到0,开始依次出栈,得到area=31,32,33,14,1*5。
    • 遍历结束。整个过程中max_space=10
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Runtime: 60 ms, faster than 97.59% of Python3 online submissions for Largest Rectangle in Histogram.
# Memory Usage: 9.3 MB, less than 41.22% of Python3 online submissions for Largest Rectangle in Histogram.
class Solution:
def largestRectangleArea(self, height):
height.append(0)
stack = [-1] # 添加-1是为了判断是不是进行到了最后一个
max_space = 0
for i in range(len(height)):
while height[i] < height[stack[-1]]: # 如果当前柱比栈顶柱要低,出栈,更新结果
h = height[stack.pop()]
w = i - stack[-1] - 1
max_space = max(max_space, h * w)
stack.append(i)
return max_space
  • 说明:
    • height升序则入栈,否则出栈计算并更新结果
    • stack存储的是height的下标
    • 栈变化如下:
1
2
3
4
5
6
7
[-1]
[-1, 0]
[-1, 1]
[-1, 1, 2]
[-1, 1, 2, 3]
[-1, 1, 4]
[-1, 1, 4, 5]

85. Maximal Rectangle

题意

给定一个填充了0和1的二维二进制矩阵,找到只包含1的最大矩形并返回其面积。
实例:

1
2
3
4
5
6
7
8
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6

思路
  • 对于某一行,将它转换成以当前行为底的直方图,而且下一个行可以根据上一行的结果直接求得高度,所以遍历完成以后,就能得到最大的矩形。
  • 进行一下模拟:
    • 第一行,对应的高度为 1 0 1 0 0
    • 第二行,对应的高度为 2 0 2 1 1
    • 第三行,对应的高度为 3 1 3 2 2
    • 第四行,对应的高度为 4 0 0 3 0
  • 其实就是,对于每一行,如果它为1,就加上上一行的高度,否则高度就为0,求得高度以后,用上一个问题的解法直接求得面积并且更新结果就可以了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Runtime: 80 ms, faster than 96.81% of Python3 online submissions for Maximal Rectangle.
# Memory Usage: 7.6 MB, less than 52.71% of Python3 online submissions for Maximal Rectangle.
class Solution:
def maximalRectangle(self, matrix):
if not matrix: return 0
height = [0] * (len(matrix[0]) + 1)
ans = 0
for row in matrix:
for i in range(len(matrix[0])):
height[i] = height[i] + 1 if row[i] == '1' else 0
stack = [-1]
for i in range(len(matrix[0]) + 1):
while height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - 1 - stack[-1]
ans = max(ans, h * w)
stack.append(i)
return ans
Donate comment here