LeetCode 42. 接雨水

42. 接雨水

解题思路

统计每个柱子的左侧和右侧最高柱子高度，积水量等于左右最高柱子较小的那个减去当前柱子高度

参考代码

class Solution {
    public int trap(int[] height) {
        int n = height.length;

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for(int i = 1; i < n; i ++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; i --) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }

        int res = 0;
        for(int i = 1; i < n - 1; i ++) {
          // 如果当前柱子高度大于等于左边最高柱子或者右边最高柱子，则无法积水
            if(height[i] >= leftMax[i - 1] || height[i] >= rightMax[i + 1]) {
                continue;
            } else {
                // 积水量等于左右最高柱子较小的那个减去当前柱子高度
                res += Math.min(leftMax[i - 1], rightMax[i + 1]) - height[i];
            }
        }
        return res;
    }
}