番禺论坛网站建设,网站导航栏代码,杭州模板做网站,建立个人网站服务器描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图#xff0c;在这种情况下#xff0c;可以接 6 个单位的雨水#xff08;蓝色部分表示雨水计算按此排列的柱子下雨之后能接多少雨水。 上面是由数组 [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 题解
思路双指针分别从左右两边遍历直到指针相遇。哪边的当前高度比较小就更新哪边结果是左右两边遍历下来最大高度和当前高度之差的总和。
class Solution {public int trap(int[] height) {if(height.length 0){return 0;}int i 0, j height.length-1;int hl height[i], hr height[j];int ml hl, mr hr;int ans 0;while(i j){if(hl hr){hr height[j];mr Math.max(hr,mr);if(hr mr){ans (mr-hr);}j--;}else{hl height[i];ml Math.max(hl,ml);if(hl ml){ans (ml-hl);}i;}}return ans;}
}
