代码随想录算法训练营第五十九天| 503.下一个更大元素II 42. 接雨水

503.下一个更大元素II

42. 接雨水 

暴力双指针

class Solution:def trap(self, height: List[int]) -> int:res = 0for i in range(1, len(height)-1):left_bar, right_bar = height[i], height[i]for j in range(i+1, len(height)):if height[j] > right_bar:right_bar = height[j]for z in range(i-1, -1, -1):if height[z] > left_bar:left_bar = height[z]h = min(right_bar, left_bar) - height[i]res += hreturn res

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

可以从行和列接雨水，从列接雨水的逻辑比较清晰，因为宽度一定是1所以只需要计算高度就行了。

想要计算一列能够接多少雨水，和木桶问题很像，取决于两边较矮的那个边的长度。

所以对于每一列，只需要首先将left_bar，right_bar初始化为当前的高度，然后依次向左和向右遍历，只要找到比左bar和右bar更高的bar就更新。

最后计算的时候，取两者的较小然后减去当前的高度 h = min(right_bar, left_bar) - height[i]。

卡哥的代码里最后还加了个判断h大于0的if，这个没必要哈因为left_bar和right_bar只有比height[i]大的时候才更新，没找到就是它自己，所以最差情况也是0，不可能小于0。

双指针优化

class Solution:def trap(self, height):if len(height) <= 2:return 0size = len(height)max_left = [0] * sizemax_right = [0] * size# Record the maximum height to the left of each barmax_left[0] = height[0]for i in range(1, size):max_left[i] = max(height[i], max_left[i - 1])# Record the maximum height to the right of each barmax_right[size - 1] = height[size - 1]for i in range(size - 2, -1, -1):max_right[i] = max(height[i], max_right[i + 1])# Calculate the total trapped watertotal_water = 0for i in range(size):water_at_bar = min(max_left[i], max_right[i]) - height[i]total_water += water_at_barreturn total_water

• 时间复杂度：O(n)
• 空间复杂度：O(n)

在暴力方法中，我们每到一个位置都要计算它左边和右边的最高bar，这里就会涉及很多重复计算。如果我们把每个点的左右最高bar首先计算出来保存在两个数组中，在循环过程中使用这个数组中的值就避免了重复运算。

单调栈

class Solution:def trap(self, height: List[int]) -> int:stack = [0]result = 0for i in range(1, len(height)):while stack and height[i] > height[stack[-1]]:mid_height = stack.pop()if stack:# 雨水高度是 min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度h = min(height[stack[-1]], height[i]) - height[mid_height]# 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1w = i - stack[-1] - 1# 累计总雨水体积result += h * wstack.append(i)return result

• 时间复杂度：O(n)
• 空间复杂度：O(n)

首先明确单调栈是按行来接雨水的：

然后确定单调栈是递增还是递减，这道题中是从栈头到栈尾单调递增。因为如果遇到了比前一个高的元素，说明遇到了桶的右bar，这时候就要pop来进行操作了。

分三种情况：

1. 如果当前元素小于前一个元素，直接入栈并保持单调递增。

2. 如果当前元素等于前一个元素，5543的情况，我们在后续计算雨水体积的时候，肯定也是用右侧的两个5的第二个5来计算，所以先pop再append。

3. 如果当前元素大于前一个元素，开始操作了。

- 首先pop获取上一个元素的高度，赋值给mid变量

- 计算高度，高度为当前元素 i 和当前栈头，也就是 i - 2的高度的较小值

- 计算宽度，宽度就是当前元素下标 i 减去栈头，再加1。假设当前元素下标为5，栈头为3，那么

5 - 3 - 1 = 1，宽度也只是1，符合题意。

- 将长乘以宽的体积计入结果变量res中。