mirror of
https://github.com/prdlk/leetcode.git
synced 2026-11-02 13:12:44 +00:00
57 lines
1.3 KiB
Python
57 lines
1.3 KiB
Python
"""
|
|
42. Trapping Rain Water
|
|
Difficulty: Hard
|
|
https://leetcode.com/problems/trapping-rain-water/
|
|
|
|
──────────────────────────────────────────────────
|
|
|
|
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 1:
|
|
|
|
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
|
|
Output: 6
|
|
Explanation: The above elevation map (black section) 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.
|
|
|
|
Example 2:
|
|
|
|
Input: height = [4,2,0,3,2,5]
|
|
Output: 9
|
|
|
|
|
|
|
|
Constraints:
|
|
|
|
• n == height.length
|
|
|
|
• 1 <= n <= 2 * 10^4
|
|
|
|
• 0 <= height[i] <= 10^5
|
|
"""
|
|
|
|
|
|
class Solution:
|
|
def trap(self, height: list[int]) -> int:
|
|
left, right = 0, len(height) - 1
|
|
leftMax, rightMax = 0, 0
|
|
total = 0
|
|
|
|
while left < right:
|
|
leftMax = max(leftMax, height[left])
|
|
rightMax = max(rightMax, height[right])
|
|
|
|
if height[left] < height[right]:
|
|
total += leftMax - height[left]
|
|
left += 1
|
|
else:
|
|
total += rightMax - height[right]
|
|
right -= 1
|
|
|
|
return total
|