0042. 接雨水

0042. 接雨水 #

  • 标签:栈、数组、双指针、动态规划、单调栈
  • 难度:困难

题目大意 #

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,用数组 height 表示,其中 height[i] 表示第 i 根柱子的高度。

要求:计算按此排列的柱子,下雨之后能接多少雨水。

解题思路 #

讲解一下使用单调栈的解法。

  • 遍历高度数组 height
  • 如果当前柱体高度较小,小于等于栈顶柱体的高度,则将当前柱子高度入栈。
  • 如果当前柱体高度较大,大于栈顶柱体的高度,则一直出栈,直到当前柱体小于等于栈顶柱体的高度。
  • 假设当前柱体为 C,出栈柱体为 B,出栈之后新的栈顶柱体为 A。则说明:
    • 当前柱体 C 是出栈柱体 B 向右找到的第一个大于当前柱体高度的柱体,那么以出栈柱体 B 为中心,可以向右将宽度扩展到当前柱体 C
    • 新的栈顶柱体 A 是出栈柱体 B 向左找到的第一个大于当前柱体高度的柱体,那么以出栈柱体 B 为中心,可以向左将宽度扩展到当前柱体 A
  • 出栈后,以新的栈顶柱体 A 为左边界,以当前柱体 C 为右边界,以左右边界与出栈柱体 B 的高度差为深度,计算可以接到雨水的面积。然后记录并更新累积面积。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        stack = []
        size = len(height)
        for i in range(size):
            while stack and height[i] > height[stack[-1]]:
                cur = stack.pop(-1)
                if stack:
                    left = stack[-1] + 1
                    right = i - 1
                    high = min(height[i], height[stack[-1]]) - height[cur]
                    ans += high * (right - left + 1)
                else:
                    break
            stack.append(i)
        return ans
本站总访问量  次  |  您是本站第  位访问者