解法都在代码里,不懂就留言或者私信
class Solution {/**本题的解题思路是双指针:一个从头开始一个从尾巴开始,两头的肯定是没有办法接住雨水的,你可以认为0位置左边是0的柱子所以理论上我们是从1遍历到n-2,但是你也可以遍历0到N-1,两种方式的不用我们设置的变量值也不同以我从1~n-2遍历来说,我先把lMax设置为heigh[0], rMax设置为height[height.lenght - 1]如果以0~N-1遍历来说,两个变量都设置为0遍历的过程中比较lMax和rMax的大小,lMax小结算左边,rMax小的话结算右边如果lMax和rMax相同则两个都结算,所以遍历过程中很可能出现每次计算两个的情况,比如[5,1,1,2,3,4,5]左边结算时用Math.max(0, lMax-height[left]),右边使用Math.max(0, rMax-height[right])这样结算的原理是就算只有两根柱子,我们要结算的柱子加上水也至少可以到达短的那个柱子的高度但是就算中间有更高的柱子,根据木桶原理,也确实只能放这么多*/public int trap(int[] height) {/**空的或者只有两个及以下的柱子是放不了水的,因为我们认为边缘的柱子高度都是0 */if(height == null || height.length <= 2){return 0;}/**左边从1开始,右边从height.length-2开始 */int left = 1;int right = height.length - 2;/**lMax, rMax代表目前为止左右柱子的最大高度 */int lMax = height[0];int rMax = height[height.length - 1];int ans = 0;while(left < right) {/**lMax小计算左边,rMax大更新右边,中间记得尝试更细lMax和rMax*/if(lMax < rMax) {ans += Math.max(0, lMax - height[left]);lMax = Math.max(lMax, height[left ++]);} else if(rMax < lMax) {ans += Math.max(0,rMax - height[right]);rMax = Math.max(rMax, height[right --]);} else {ans += Math.max(0,lMax - height[left]);ans += Math.max(0,rMax - height[right]);lMax = Math.max(lMax, height[left ++]);rMax = Math.max(rMax, height[right--]);}}/**如果最后是因为left=right退出的,需要单独结算一下这个位置 */if(left == right) {ans += Math.max(0, Math.min(lMax, rMax) - height[left]);}return ans;}
}
运行结果