LeetCode.42.接雨水

[toc]

题目描述

给定 n 个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

动态规划思路

solution one: 动态规划

• 数组leftMaxs用于存放当前i的左边柱子的最大值 ,leftMaxs[i]表示第i个位置左边柱子的最大值
• 数组rightMaxs用于存放当前i的右边柱子的最大值 rigthMaxs[i]表示第i个位置右边柱子的最大值
  • 那么： n=height.length;
    leftMaxs[0] = height[0];
    rightMaxs[n-1] = height[n-1];
• leftMaxs[i] = max(leftMaxs[i-1],height[i]);
• rightMaxs[i] = max(rightMaxs[i+1],height[i]);

• 那么当前index的最大水量为 左边柱子最大值和右边柱子最大值之间的最小值减去当前位置柱子高度

  • 即: result = Math.min(leftMaxs[i],rightMaxs[i]) - height[i]

    代码实现

    class Solution {
    public int trap(int[] height) {
       // solution one: 动态规划
       // 数组leftMaxs用于存放当前i的左边柱子的最大值 leftMaxs[i]表示第i个位置左边柱子的最大值
       // 数组rightMaxs用于存放当前i的右边柱子的最大值 rigthMaxs[i]表示第i个位置右边柱子的最大值
       // 那么： n=height.length;
       //      leftMaxs[0] = height[0]; rightMaxs[n-1] = height[n-1];
       // leftMaxs[i] = max(leftMaxs[i-1],height[i]);
       // rightMaxs[i] = max(rightMaxs[i+1],height[i]);
       // 那么当前index的最大水量为 左边柱子最大值和右边柱子最大值之间的最小值减去当前位置柱子高度
       //      即: result = Math.min(leftMaxs[i],rightMaxs[i]) - height[i]
       int n = height.length;
       if(n==0) return 0;
       int[] leftMaxs = new int[n];
       int[] rightMaxs = new int[n];
       leftMaxs[0] = height[0];
       rightMaxs[n-1] = height[n-1];
       // 遍历，找出每个index的左右边柱子的最大值
       for(int i=1;i<n;i++){
           leftMaxs[i] = Math.max(leftMaxs[i-1],height[i]);
           rightMaxs[n-1-i] = Math.max(rightMaxs[n-i],height[n-1-i]);
       }
       int res = 0;
       for(int i=0;i<n;i++){
           res += Math.min(leftMaxs[i],rightMaxs[i])-height[i];
       }
       return res;
    }
    }