42. Trapping Rain Water
計算下雨後可以蓄積多少水。
範例 1：
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 輸出：6 解釋：上面的高程圖（黑色部分）由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示。在這種情況下，6 單位的雨水（藍色部分）被困住。
Python
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water_trapped = 0
while left < right:
if left_max < right_max:
left += 1
left_max = max(left_max, height[left])
water_trapped += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
water_trapped += right_max - height[right]
return water_trapped
18.35MB, 78ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
if (height.empty()) {
return 0;
}
int left = 0, right = height.size() - 1;
int left_max = height[left], right_max = height[right];
int water_trapped = 0;
while (left < right) {
if (left_max < right_max) {
left++;
left_max = max(left_max, height[left]);
water_trapped += left_max - height[left];
} else {
right--;
right_max = max(right_max, height[right]);
water_trapped += right_max - height[right];
}
}
return water_trapped;
}
};
22.25MB, 14ms
Javascript
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
if (height.length === 0) {
return 0;
}
let left = 0, right = height.length - 1;
let leftMax = height[left], rightMax = height[right];
let waterTrapped = 0;
while (left < right) {
if (leftMax < rightMax) {
left++;
leftMax = Math.max(leftMax, height[left]);
waterTrapped += leftMax - height[left];
} else {
right--;
rightMax = Math.max(rightMax, height[right]);
waterTrapped += rightMax - height[right];
}
}
return waterTrapped;
};
49.76MB, 49ms
