代码随想录算法训练营第四十九天｜ 42. 接雨水 、84.柱状图中最大的矩形 ...

42. Trapping Rain Water

双指针暴力解法：
每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度，即： min(lHeight, rHeight) - height

1. class Solution:
2.     def trap(self, height):
3.         if len(height) <= 2:
4.             return 0
6.         max_left = [0] * len(height)
7.         max_right = [0] * len(height)
8.         n = len(height)
10.         # 记录每个柱子左边柱子最大高度
11.         max_left[0] = height[0]
12.         for i in range(1, n):
13.             max_left[i] = max(height[i], max_left[i - 1])
15.         # 记录每个柱子右边柱子最大高度
16.         max_right[n - 1] = height[n - 1]
17.         for i in range(n - 2, -1, -1):
18.             max_right[i] = max(height[i], max_right[i + 1])
20.         # 求和
21.         sum_ = 0
22.         for i in range(n):
23.             count = min(max_left[i], max_right[i]) - height[i]
24.             if count > 0:
25.                 sum_ += count
27.         return sum_
28.         

复制代码

单调栈解法：
一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
遇到类似的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中，因为我们要求宽度的时间 如果遇到类似高度的柱子，需要利用最右边的柱子来计算宽度。

1. class Solution:
2.     def trap(self, height):
3.         result = 0
4.         stack = [0]
5.         for i in range(1, len(height)):
6.             while len(stack) > 0 and height[i] > height[stack[-1]]:
7.                 mid_height = stack.pop()
8.                 if stack:
9.                     h = min(height[i], height[stack[-1]]) - height[mid_height]
10.                     w = i - stack[-1] - 1
11.                     v = h*w
12.                     result += v
13.             stack.append(i)
14.         return result

复制代码

84. Largest Rectangle in Histogram

只有栈里从大到小的顺序，才能包管栈顶元素找到左右双方第一个小于栈顶元素的柱子。
所以本题单调栈的顺序恰恰与接雨水反过来。
此时大家应该可以发现实在就是栈顶和栈顶的下一个元素以及要入栈的三个元素构成了我们要求最大面积的高度和宽度

1. # 单调栈精简
2. class Solution:
3.     def largestRectangleArea(self, heights: List[int]) -> int:
4.         heights.insert(0, 0)
5.         heights.append(0)
6.         stack = [0]
7.         result = 0
8.         for i in range(1, len(heights)):
9.             while stack and heights[i] < heights[stack[-1]]:
10.                 mid_height = heights[stack[-1]]
11.                 stack.pop()
12.                 if stack:
13.                     # area = width * height
14.                     area = (i - stack[-1] - 1) * mid_height
15.                     result = max(area, result)
16.             stack.append(i)
17.         return result

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。