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
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

Donate article here
Share the post