42. Trapping Rain Water
Stack, Array, Two Pointers, DP, Monotonic Stack, AMateList ·Problem Statement
link: LeetCode.cn LeetCode Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints: n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5
Solution Approach
The solution calculates the water trapped by iterating from both ends toward the highest bar, accumulating water based on the difference between the current height and the maximum height encountered so far.
Algorithm
Identify the maximum height bar and divide the problem into two parts: left of the max bar and right of the max bar. Traverse from the left to the maximum bar, accumulating water by comparing each bar to the maximum bar encountered on the left. Similarly, traverse from the right to the maximum bar, accumulating water based on the maximum bar encountered on the right.
Complexity
time complexity: O(n) space complexity: O(1)
Implement
class Solution:
def trap(self, height: List[int]) -> int:
maxbar = max(height)
maxIdx = height.index(maxbar)
l = maxl = 0
r = maxr = len(height) - 1
w = 0
while l < maxIdx:
if height[l] < height[maxl]:
w += (height[maxl] - height[l])
else:
maxl = l
l += 1
while r > maxIdx:
if height[r] < height[maxr]:
w += (height[maxr] - height[r])
else:
maxr = r
r -= 1
return w