leetcode 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

javascript:

/** * @param {number[]} height * @return {number} */ var trap = function(height) { let left = 0; // 左侧指针 let right = height.length - 1;// 右侧指针 let [leftMax, rightMax, result] = [0,0,0]; // leftMax：左边的最大值，它是从左往右遍历找到的 // rightMax：右边的最大值，它是从右往左遍历找到的 while(left < right){ if(height[left] < height[right]){ if(leftMax < height[left]){ leftMax = height[left]; }else{ // 在某个位置处，它能存的水，取决于它左右两边的最大值中较小的一个。 result += leftMax - height[left]; } left++; }else{ if(rightMax < height[right]){ rightMax = height[right]; }else{ // 在某个位置处，它能存的水，取决于它左右两边的最大值中较小的一个。 result += rightMax - height[right]; } right --; } } return result; };

java:

class Solution { public int trap(int[] height) { int left = 0, right = height.length - 1, leftMax = 0, rightMax = 0, sum = 0; while(left < right){ if(height[left] < height[right]){ if(leftMax < height[left]){ leftMax = height[left]; }else{ sum += leftMax - height[left]; } left ++; }else{ if(rightMax < height[right]){ rightMax = height[right]; }else{ sum += rightMax - height[right]; } right --; } } return sum; } }