LeetCode：接雨水【42】

题目描述

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

　　

　　上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

　　输入: [0,1,0,2,1,0,1,3,2,1,2,1]
　　输出: 6

题目分析

简要思路

1. 找出最高点
2. 分别从两边往最高点遍历：如果下一个数比当前数小，说明可以接到水　　

视频分析

　　

Java题解

class Solution {

    public int trap(int[] height) {

        int result = 0;

        int maxValue = -1;

        int maxAddr = 0;

        for(int i = 0;i<height.length;i++){

            if(height[i]>=maxValue){

                maxValue = height[i];maxAddr=i;

            }

        }

        //左半部分处理

        for(int left = 0;left<maxAddr;left++){

            for(int i =left+1;i<=maxAddr;i++){

                if(height[i]<height[left])

                    result=result+(height[left]-height[i]);

                else

                    left = i;

            }

        }

        //右半部分处理

        for(int right =height.length-1;right>maxAddr;right--){

            for(int i =right-1;i>=maxAddr;i--){

                if(height[i]<height[right])

                    result=result+(height[right]-height[i]);

                else

                    right = i;

            }

        }

        return result;

    }

}