Учитывая n
неотрицательных целых чисел, представляющих карту высот, где ширина каждой полосы равна 1
, вычислите, сколько воды она может собрать после дождя.
Пример 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.
Пример 2:
Input: height = [4,2,0,3,2,5] Output: 9
Ограничения:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Решения:
Питон
class Solution: def trap(self, height: List[int]) -> int: if not height: return 0 n = len(height) left, right = 0, n - 1 left_max, right_max = height[left], height[right] ans = 0 while left < right: if left_max < right_max: ans += left_max - height[left] left += 1 left_max = max(left_max, height[left]) else: ans += right_max - height[right] right -= 1 right_max = max(right_max, height[right]) return ans
C#
class Solution { public int Trap(int[] height) { if (height.Length == 0) { return 0; } int n = height.Length; int left = 0, right = n - 1; int leftMax = height[left], rightMax = height[right]; int ans = 0; while (left < right) { if (leftMax < rightMax) { ans += leftMax - height[left]; left++; leftMax = Math.Max(leftMax, height[left]); } else { ans += rightMax - height[right]; right--; rightMax = Math.Max(rightMax, height[right]); } } return ans; } }
Ява
class Solution { public int trap(int[] height) { if (height.length == 0) { return 0; } int n = height.length; int left = 0, right = n - 1; int leftMax = height[left], rightMax = height[right]; int ans = 0; while (left < right) { if (leftMax < rightMax) { ans += leftMax - height[left]; left++; leftMax = Math.max(leftMax, height[left]); } else { ans += rightMax - height[right]; right--; rightMax = Math.max(rightMax, height[right]); } } return ans; } }
JavaScript
/** * @param {number[]} height * @return {number} */ var trap = function(height) { if (height.length === 0) { return 0; } let n = height.length; let left = 0, right = n - 1; let leftMax = height[left], rightMax = height[right]; let ans = 0; while (left < right) { if (leftMax < rightMax) { ans += leftMax - height[left]; left++; leftMax = Math.max(leftMax, height[left]); } else { ans += rightMax - height[right]; right--; rightMax = Math.max(rightMax, height[right]); } } return ans; };
Типографический текст
function trap(height: number[]): number { if (height.length === 0) { return 0; } let n = height.length; let left = 0, right = n - 1; let leftMax = height[left], rightMax = height[right]; let ans = 0; while (left < right) { if (leftMax < rightMax) { ans += leftMax - height[left]; left++; leftMax = Math.max(leftMax, height[left]); } else { ans += rightMax - height[right]; right--; rightMax = Math.max(rightMax, height[right]); } } return ans; }
PHP
class Solution { /** * @param Integer[] $height * @return Integer */ function trap($height) { if (count($height) === 0) { return 0; } $n = count($height); $left = 0; $right = $n - 1; $leftMax = $height[$left]; $rightMax = $height[$right]; $ans = 0; while ($left < $right) { if ($leftMax < $rightMax) { $ans += $leftMax - $height[$left]; $left++; $leftMax = max($leftMax, $height[$left]); } else { $ans += $rightMax - $height[$right]; $right--; $rightMax = max($rightMax, $height[$right]); } } return $ans; } }
Надеюсь, это поможет! Дайте знать, если у вас появятся вопросы. Не забудьте подписаться и похлопать в поддержку моего контента