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解：很抽象，双指针，主要是要理解为什么左边最大值大于右边最大值时候，右指针要往左移动，而不是左指针继续往右移动。也可以这样做：先循环找出整个数组最大值，分成两边，分别向这个最大值遍历。
public int trap(int[] height) {
int res = 0;
if (height == null || 0 == height.length) {
return res;
}
int len = height.length;
int l = 0;
int r = len - 1;
int lmax = 0;
int rmax = 0;
while (l < r) {
lmax = Math.max(lmax, height[l]);
rmax = Math.max(rmax, height[r]);
if (lmax > rmax) {
res += rmax - height[r];
r--;
} else {
res += lmax - height[l];
l++;
}
}
return res;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-07-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读