leetcode-42. 接雨水

JAVA解法

class Solution {
    public int trap(int[] height) {
        // 定义 ans 为最终接雨水的量
        int ans = 0;
        // 定义左右边界的位置，即左右双指针
        int left = 0, right = height.length - 1;
        // 定义记录左右边界的最大高度
        int leftMax = 0, rightMax = 0;
        // 当左边界小于右边界时进入循环
        while (left < right) {
            // 取传进来的高度与已记录的左侧最大高度这两个值较大的一个作为左边界
            leftMax = Math.max(leftMax, height[left]);
            // 取传进来的高度与已记录的右侧最大高度这两个值较大的一个作为右边界
            rightMax = Math.max(rightMax, height[right]);
            // 如果左侧指针的值小于右侧指针的值
            if (height[left] < height[right]) {
                // 可接雨水的量为左侧最高的值即左边界减去右侧指针的值，木桶的短板效应
                ans += leftMax - height[left];
                // 此时要向着高的木板那一侧靠近
                ++left;
                // 假如此时右侧的木板小于左侧的木板
            } else {
                // 可接雨水的量为右侧最高的值即右边界减去左侧指针的值
                ans += rightMax - height[right];
                // 此时要向着高的木板那一侧靠近
                --right;
            }
        }
        // 最后返回能接雨水的量
        return ans;
    }
}

题解分析

  这道题用的是双指针，利用著名的木桶短板效应，两个指针初始化在左右两边界，先让左指针往右移动一个单位，然后把此时的值与右指针的值进行比较。若左侧的值大于右侧，则把左侧当前的值记为当前最高的一块木板，同理若右侧的值大于左侧，则把右侧当前的值记为当前最高的一块木板。用大的值减去小的值即为此时可盛水的量，若两边的高度一样则可盛水的量为 0，继续移动指针，让矮的木板的一侧的指针向目前最高的那块板的方向移动，若左右木板同样高，则让左边的向右边靠，最后两个指针相遇则可盛水的量也就算出来了。方法相当巧妙，运行效率也是相当高，挺好玩的一道题，第一次做困难不觉得难受。

leetcode原题：42. 接雨水