leetcode 42. Trapping Rain Water（接雨水）

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

给出一个数组代表不同bar的高，问bar之间能聚多少水

思路：
每个bar处雨水的多少=min（左边最高的bar，右边最高的bar）-当前bar的高度，最后对所有bar求和
因为雨水的多少是由左右短板决定的，找出左边最高的bar和右边最高的bar，它们中较小的决定了当前bar处的雨水量，当前bar处可积的雨水量就是左右bar中最小的减去当前bar的高度

本来是在每个bar处都遍历左右，找到左边max和右边max，取较小的减去当前bar的高度，对所有bar求和。但是可以看到有很多重复计算，因为每遍历一个元素都要求一遍左右max，时间复杂度为O(N²)

减少重复计算可以用双指针，从两边开始遍历，因为积水量受短板影响，所以短的那一端指针移动，以保留较长的，
注意判断哪边短其实也就相当于选了左右max中较小的（因为max如果较大，这个指针是不会移动的），也选取了当前bar，
用左右max中较小的减去当前指针所指的bar的长度，
对所有的bar处求和

    public int trap(int[] height) {if(height == null || height.length == 0) {return 0;}int n = height.length;int left = 0;int right = n - 1;int result = 0;int leftMax = 0;int rightMax = 0;while(left < right) {if(height[left] < height[right]) {leftMax = Math.max(leftMax, height[left]);result += leftMax - height[left];left ++;} else {rightMax = Math.max(rightMax, height[right]);result += rightMax - height[right];right --;}}return result;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！