leetcode42：接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
动态编程-->O(n) O(n)
public int trap(int[] height) { if (height == null || height.length == 0) return 0; int ans = 0; int size = height.length; int[] left_max = new int[size]; int[] right_max = new int[size]; left_max[0] = height[0]; for (int i = 1; i < size; i++) { left_max[i] = Math.max(height[i], left_max[i - 1]); } right_max[size - 1] = height[size - 1]; for (int i = size - 2; i >= 0; i--) { right_max[i] = Math.max(height[i], right_max[i + 1]); } for (int i = 1; i < size - 1; i++) { ans += Math.min(left_max[i], right_max[i]) - height[i]; } return ans; }
单调栈-->O(n) O(n)
class Solution:
def trap(self, height: List[int]) -> int:
stack = []
stack.append(0)
res = 0
for i in range(1, len(height)):
while stack and height[stack[-1]] <= height[i]:
x = stack.pop()
if not stack:
break
res += (min(height[stack[-1]], height[i]) - height[x]) * (i - stack[-1] - 1)
stack.append(i)
return res
双指针
public int trap(int[] height) { int left = 0, right = height.length - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { ans += (left_max - height[left]); } ++left; } else { if (height[right] >= right_max) { right_max = height[right]; } else { ans += (right_max - height[right]); } --right; } } return ans; }