【数据结构与算法】单调栈

发表于 更新于 分类于 阅读次数：
本文字数： 3.7k 阅读时长 ≈ 3 分钟

参考《程序员面试指南：IT名企算法于数据结构题目最优解（第2版）》

单调栈

单调栈是一种从栈顶到栈底单调递增或单调递减的栈。
它常用于解决离某位置最近的最大或者最小值这种问题。

不含重复值的数组

问题描述

给定一个不含重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置。返回所有位置相应的信息，不存在则为-1。

示例：
输入：arr = [3, 4, 1, 5, 6, 2, 7]
输出：[(-1, 2), (0, 2), (-1, -1), (2, 5), (3, 5), (2, -1), (5, -1)]

暴力解法

时间复杂度为$\mathcal{O}(N^2)$，每个位置分别向左和向右遍历即可。

单调栈解法

时间复杂度为$\mathcal{O}(N)$。
大致思路是维护一个单调栈stack和结果数组res，因为是找最小值，所以为从栈顶到栈底单调递减的栈，栈中保存的是arr中的位置。

  • 如果当前遍历到的值比栈顶元素对应arr中的值大，那么直接入栈；
  • 若比栈顶元素对应arr中的值小，那么弹出栈顶元素对应的结果就可确定了，当前遍历的值为其右边最近且比它小的值，新的栈顶元素为其左边最近且比它小的值。
  • 如果arr中元素已经遍历完则判断stack是否为空，若为空，则已经得到最终的结果了，若stack不为空，则需要一次弹出stack的栈顶元素，此时剩下的这些元素不存在位于其右边且比之小的值，所以全部为-1，而只要还有新的栈顶元素即为其左边且比之小的值，如果弹出当前元素后为空，则其res中的值为(-1, -1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
arr = [3, 4, 1, 5, 6, 2, 7]
n = len(arr)
stack, res = [], [None] * n

for i in range(n):
    while stack and arr[i] < arr[stack[-1]]:
        cur = stack.pop()
        left_less = -1 if not stack else stack[-1]
        res[cur] = (left_less, i)

    stack.append(i)

while stack:
    cur = stack.pop()
    left_less = -1 if not stack else stack[-1]
    res[cur] = (left_less, -1)
print('arr: ', arr)
print('res: ', res)
"""
arr:  [3, 4, 1, 5, 6, 2, 7]
res:  [(-1, 2), (0, 2), (-1, -1), (2, 5), (3, 5), (2, -1), (5, -1)]
"""

含重复值的数组

问题描述

题目和上述不含重复值类似，只是去掉了不含重复值的条件。

示例：
输入：arr = [3, 1, 3, 4, 3, 5, 3, 2, 2]
输出：[(-1, 1), (-1, -1), (1, 7), (2, 4), (1, 7), (4, 6), (1, 7), (1, -1), (1, -1)]

暴力解法

暴力解法思路与不含重复值相同

单调栈解法

整体思路一样，只不过单调栈中的元素不再是单个值而是一个整型数组，如果遇到栈顶元素对应arr中的值与当前遍历到的元素对应arr中的值相同则将其位置添加到栈顶的数组/列表当中。当弹出一个栈顶数组时，数组中的元素对应res中的结果均一样，取值方法与上述不含重复值一致，唯一需要注意的点是取新的栈顶元素作为左边最近且比它小的值时一定要取列表中最后一个元素即最晚加入的元素，这样保证是左边最近。

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
arr= [3, 1, 3, 4, 3, 5, 3, 2, 2]
n = len(arr)
stack, res = [], [None] * n

for i in range(n):
    while stack and arr[i] < arr[stack[-1][0]]:
        cur = stack.pop()
        for idx in cur:
            left_less = -1 if not stack else stack[-1][-1]
            res[idx] = (left_less, i)
    if stack and arr[i] == arr[stack[-1][0]]:
        stack[-1].append(i)
    else:
        stack.append([i])

while stack:
    cur = stack.pop()
    for idx in cur:
        left_less = -1 if not stack else stack[-1][-1]
        res[idx] = (left_less, -1)

print('arr: ', arr)
print('res: ', res)
"""
arr:  [3, 1, 3, 4, 3, 5, 3, 2, 2]
res:  [(-1, 1), (-1, -1), (1, 7), (2, 4), (1, 7), (4, 6), (1, 7), (1, -1), (1, -1)]
"""

求最大子矩阵的大小

题目描述

给定一个整型矩阵map，其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域的面积（即其中1的数量）。

示例1:
输入：[1, 1, 1, 0]
输出：3

示例2:
输入：[[1, 0, 1, 1], [1, 1, 1, 1], [1, 1, 1, 0]]
输出：6

思路及解法

  1. 设一个高度数组height，里面存着每一行以当前行为底的情况下，每个位置往上的连续1的数量。比如示例2的对一个height数组为[[1, 0, 1, 1], [2, 1, 2, 2], [3, 2, 3, 0]]。更新公式为height[i][j] = 0 if height[i-1][j] == 0 else height[i-1][j] + 1。
  2. 对于height中的某一行来说，以该行某一个元素为高，用单调栈来求出它左右两边离它最近的比它小的元素(m, n)，那么最大矩阵的宽即为n-1-(m+1)+1 = n-m-1，矩形面积为(n-m-1)*height[i][j]。依次遍历height的每一行的每一个元素即可以得到最终最大矩形的面积。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def max_rect_from_bottom(height):
    max_area, n = 0, len(height)
    stack = []

    for i in range(n):
        while stack and height[i] < height[stack[-1][0]]:
            cur = stack.pop()
            for idx in cur:
                left_less = -1 if not stack else stack[-1][-1]
                max_area = max(max_area, (i - left_less-1)*height[idx])
        if stack and height[i] == height[stack[-1][0]]:
            stack[-1].append(i)
        else:
            stack.append([i])

    while stack:
        cur = stack.pop()
        for idx in cur:
            left_less = -1 if not stack else stack[-1][-1]
            max_area = max(max_area, (n - left_less)*height[idx])
    return max_area
map_ = [
       [1, 0, 1, 1], 
       [1, 1, 1, 1], 
       [1, 1, 1, 0],
       [1, 1, 1, 0], 
       [1, 1, 0, 0], 
       [0, 1, 1, 1]
      ]
m, n = len(map_), len(map_[0])
height = [map_[0]] + [[0]*n for _ in range(m-1)]
max_area = 0

for i in range(1, m):
    for j in range(n):
        if map_[i][j] == 0:
            height[i][j] = 0
        else:
            height[i][j] = 1 if map_[i-1][j] == 0 else height[i-1][j] + 1
    max_area = max(max_area, max_rect_from_bottom(height[i]))
print('map_:')
[print(f'\t{m}') for m in map_]
print('height: ')
[print(f'\t{h}') for h in height]
print('max area: ', max_area)
"""
map:
    [1, 0, 1, 1]
    [1, 1, 1, 1]
    [1, 1, 1, 0]
    [1, 1, 1, 0]
    [1, 1, 0, 0]
    [0, 1, 1, 1]
height: 
    [1, 0, 1, 1]
    [2, 1, 2, 2]
    [3, 2, 3, 0]
    [4, 3, 4, 0]
    [5, 4, 0, 0]
    [0, 5, 1, 1]
max area:  9
"""