su29029的博客

因为心在那里

0%

了解单调栈

Posted on Edited on In Views: Valine:
Symbols count in article: 5.1k字 Reading time ≈ 5 mins.

单调栈，顾名思义，是一种元素单调排列（递增或递减）的栈结构。单调栈要求栈中的所有元素在任意时刻都要保持其单调性。例如[1,2,3,4]是单调递增栈，[5,3,1]是单调递减栈。

举个例子，我们需要依次将数组 [1,3,4,5,2,9,6] 压入单调栈。

  1. 首先压入 1，此时的栈为：[1]
  2. 继续压入 3，此时的栈为：[1,3]
  3. 继续压入 4，此时的栈为：[1,3,4]
  4. 继续压入 5，此时的栈为：[1,3,4,5]
  5. 若继续压入 2，此时的栈为：[1,3,4,5,2] 不满足单调递减栈的特性， 因此需要调整。然而由于栈只有 pop 操作，因此我们只好不断 pop，直到满足压入2后整个栈单调递减为止。此时栈为[1,2]。
  6. 压入9，此时栈为[1,2,9]。
  7. 若继续压入 6，则不满足单调递减栈的特性， 于是继续pop，直到满足压入6整个栈单调递减为止。此时的栈为：[1,2,6]

单调栈主要适合于求解下一个大于xxx或者下一个小于xxx的问题。一般来说单调栈中存的是原数组中的元素索引，比如上面这个例子，单调栈的变化为：[]->[0]->[0,1]->[0,1,2]->[0,1,2,3]->[0,4]->[0,4,5]->[0,4,6]。第五步，当我们需要压入2时，需要进行pop操作，第一个pop出来的是5，因此 5 之后的第一个小于 5 的元素的索引就是 4。同理被 pop 出来的 3，4之后的第一个小于它的元素的索引也都是 4。

单调栈的时间复杂度为O(n)，因为要至少遍历一次原序列/数组，空间复杂度也为O(n)，因为需要辅助栈来保存索引。

例题：接雨水

这个题主体思路便是借助单调栈的特性，维护一个单调递减栈，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。这个题还需要考虑的一点是我们需要计算的是可接雨水的区域容积大小，也就是需要得到一个接雨水的区域，那么我们不能只单纯的获取栈顶元素，还需要获取栈顶元素的前一个元素，才能构成一个区域。从左到右遍历数组，遍历到下标i时，如果栈内至少有两个元素，记栈顶元素为top，top的前面一个元素是left，则一定有 height[left]≥height[top]。如果height[i]>height[top],则得到一个可以接雨水的区域，该区域的宽度是i−left−1，高度是min(height[left],height[i])−height[top]。每次计算完i处能接的雨水量后，仍需将i入栈，继续遍历。

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
func trap(height []int) int {
    var stack []int
    var res int = 0
    
    for i := 0; i < len(height); i++ {
        for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                break
            }
            
            left := stack[len(stack)-1]
            width := i-left-1
            height := min(height[i], height[left]) - height[top]
            res += width*height
        }
        stack = append(stack, i)
    }
    return res
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}