RUOCHI.AI
0%

Monotone Stack

Posted on Edited on In Valine:
the use of Monotone Stack

所谓的单调栈 Monotone Stack，就是栈内元素都是单调递增或者单调递减的。单调栈的一大优势就是线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了。

google interview

给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1） input: 5,3,1,2,4 return: -1 3 1 1 -1

  • 维护一个单调递减栈
  • 每个元素出栈，是说明它找到了它在原数组中的next greater element.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(array):
    res = [-1] * len(array)
    max_stack = []

    num2ind = {num:index for index,num in enumerate(array)}

    array = array[::-1]
    while array:
        num = array.pop()

        while max_stack and max_stack[-1] < num:
            item = max_stack.pop()
            distance = num2ind[num] - num2ind[item]
            res[num2ind[item]] = distance
        max_stack.append(num)

    return res

array = [5,3,1,2,4]
print(solution((array))) # -> [-1, 3, 1, 1, -1]

Trapping Rain Water

Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

  • 维护一个单调递减栈，每当新的高度小于等于栈顶高度，则把当前高度的坐标压入栈。
  • 注意我们不直接把高度压入栈，而是把坐标压入栈，这样方便我们在后来算水平距离。
  • 当我们遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时我们栈里至少有一个高度，如果只有一个的话，那么不能形成坑，我们直接跳过。
  • 如果多余一个或多个的话，那么此时把栈顶元素取出来当作坑，记录栈顶元素的高度t。不断弹出栈顶元素直到栈顶元素不等于坑的高度。
  • 此时栈顶元素是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量。
  • 注意不要弹出左边界，一下次该左边界可能成为坑的高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def trap(self, height: List[int]) -> int:
        i = 0
        area = 0
        s = []
        while i < len(height):
            if not s or height[i] <= height[s[-1]]:
                s.append(i)
                i+=1
            else:
                t = s.pop()
                while s and s[-1] == t:
                    s.pop()
                if not s: 
                    continue
                print(i,s)
                area += (i-s[-1]-1) * (min(height[i], height[s[-1]]) - height[t])

        return area

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

1
2
Input: [2,1,5,6,2,3]
Output: 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        max_stack = []
        heights.append(0)
        for i in range(len(heights)):
            while max_stack and heights[max_stack[-1]] >= heights[i]:
                cur = max_stack.pop()
                if not max_stack: 
                    max_area = max(max_area, heights[cur] * i)
                else:
                    max_area = max(max_area,heights[cur]*(i - max_stack[-1] - 1))
            max_stack.append(i)       
        return max_area