LeetCode – 特拉普ing Rain 沃特er

题目:

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.

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.

For example,

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Given`[0,1,0,2,1,0,1,3,2,1,2,1]`, return`6`.

图片 1

The above elevation map is represented by array
[0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue
section) are being trapped.

The above elevation map is represented by array
[0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue
section) are being trapped. Thanks Marcos for contributing this
image!

思路

  1. 分级用3个数组leftHeight,
    rightHeight分别记录当前index,它右边的最大值和右侧的最大值。
  2. 那么当前index的可以盛水量 ==
    (min(leftHeight[i], rightHeight[i]) - height[i]) * 1.
    因为盛水量有矮的墙决定,而且每种index有投机的冲天,所以必须减去他自个儿的万丈。
    Note:假诺盛水量< 0,表明相当的小概盛水,那么volume = 0
  3. 尽管获得leftHeight, rightHeight? 自左向右遍历数组, 找到leftHeight;
    自右向左遍历数组,找到rightHeight。

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
          return 0;
        }

        int len = height.length;
        int[] leftHeight = new int[len];
        int[] rightHeight = new int[len];

        int leftMax = 0;
        leftHeight[0] = 0;
        //1. 从左向右找当前index左边最大值,一旦找到当前最大值,其后的所有最大值都是这个最大值,直到找到更大的
        for (int i = 1; i < len; i++) {
          if (height[i - 1] > leftMax) {
                leftMax = height[i - 1];
              } 
            leftHeight[i] = leftMax;
        }

        //2. 从右向左找当前index右边最大值,一旦找到当前最大值,其后的所有最大值都是这个最大值,直到找到更大的
        int rightMax = 0;
        rightHeight[len - 1] = 0;
        for (int i = len - 2; i >= 0; i--) {
          if (height[i + 1] > rightMax){
            rightMax = height[i + 1];
          }
          rightHeight[i] = rightMax;
        }

        //3. 计算容量
        int result = 0;
        for (int i = 0; i < len; i++) {
          int waterTrap = Math.min(leftHeight[i], rightHeight[i]) - height[i];
          result += waterTrap > 0 ? waterTrap : 0;
        }
        return result;
    }
}

思路:

  1. 找到最高的点index

  2. 算算(0, index)和(index,
    n-1)之间各点的面积

    package area;

    public class TrappingRainWater {

     public int trap(int[] height) {
         int n;
         if (height == null || (n = height.length) == 0) return 0;
         int area = 0;
         int maxHeight = height[0];
         int maxHeightIndex = 0;
         for (int i = 1; i < n; ++i) {
             if (height[i] > maxHeight) {
                 maxHeight = height[i];
                 maxHeightIndex = i;
             }
         }
    
         int leftMax = height[0];
         for (int i = 1; i < maxHeightIndex; ++i) {
             if (height[i] > leftMax)
                 leftMax = height[i];
             area += (leftMax - height[i]);
         }
    
         int rightMax = height[n - 1];
         for (int i = n - 2; i > maxHeightIndex; --i) {
             if (height[i] > rightMax) 
                 rightMax = height[i];
             area += rightMax - height[i];
         }
    
         return area;
     }
    
     public static void main(String[] args) {
         // TODO Auto-generated method stub
         int[] height = { /*0,1,0,2,1,0,1,3,2,1,2,1*/ 5,2,1,2,1,5 };
         TrappingRainWater t = new TrappingRainWater();
         System.out.println(t.trap(height));
     }
    

    }

 

相关文章