[LeetCode] 42. Trapping Rain Water_hard tag: Two Pointers

博观而约取，厚积而薄发。这篇文章主要讲述[LeetCode] 42. Trapping Rain Water_hard tag: Two Pointers相关的知识，希望能为你提供帮助。
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.

文章图片

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.
【[LeetCode] 42. Trapping Rain Water_hard tag: Two Pointers】Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

这个题目思路类似于木桶原理, 中间能收集到的水, 取决于左右两边较短的高度, 然后分别往中间走, 直到两者相遇. 所以设置l, r, lh(left height), rh(right height), 判断l,r指向的building
那个短就移动哪个, 比如l 指的更短, 那么l+= 1, 然后如果新building比相应的left height要短, ans += left height - building[l], 否则 height = building[l], 如果r指的更短, 那么
情况类似.

1. Constraints
1) empty, edge case, return 0
2) element will be > = 0 integer

2. Ideas

Two points:T:O(n)S: O(1)

3. Code

class Solution: def trapRainWater(self, heights): if not heights: return 0 l, r, ans = 0, len(heights) -1, 0 lh, rh = heights[l], heights[r] while l < r: if heights[l] < = heights[r]: l += 1 if heights[l] < lh: ans += lh - heights[l] else: lh = heights[l] else: r -= 1 if heights[r] < rh: ans += rh - heights[r] else: rh = heights[r] return ans

4. Test cases
1) empty
2) 1, 2, 3
3)