Java算法每日一题day2：接雨水问题

1.问题描述

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

高度图

上面是由数组 [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

2.方法

直观想法

直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。

3.执行代码

class Solution {
    public int trap(int[] height) {
        int ans=0;
        for(int i=1;i<height.length-1;i++){
            int left_max=0,right_max=0;
            for(int j=i;j>=0;j--){
                left_max=max(left_max,height[j]);//向左遍历找最大值
            }
            for(int j=i;j<=height.length-1;j++){
                right_max=max(right_max,height[j]);//向右遍历找最大值
            }
            ans+=min(left_max,right_max)-height[i];//遍历到当前元素所接雨水总数
        }
        return ans;
    }
    private int max(int a, int b ) {
        if(a>b) return a;
        else return b;
    }

    private int min(int a, int b) {
        if(a<b) return a;
        else return b;
    }
}

4.复杂度分析

时间复杂度： O(n²)。数组中的每个元素都需要向左向右扫描。
空间复杂度 O(1)的额外空间。