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:DP

记录每个位置的最大左边界和右边界，然后利用dp[i] = max(dp[i], dp[i - 1])进行状态更新，使用记录的左右边界的最小值减去当前高度获取结果

思路3: 双指针法

实际上两个状态转移都只用到了一个原状态，故可以只记录左右最大值即可，在这个过程中，若左边最大值小于右边最小值，这取左边最大值减去当前值即获得当且可接雨水量

代码

思路1代码

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3){
            return 0;
        }
        int result = 0;
        int height_size = height.length;
        for(int i = 1; i < height_size - 1; i++){
            int left_height = height[i];
            int right_heigh = height[i];
            for(int j = 0; j < height_size; j++){
                if(j < i && height[j] > left_height){
                    left_height = height[j];
                }
                if (j > i && height[j] > right_heigh){
                    right_heigh = height[j];
                }
            }
            result += Math.min(left_height, right_heigh) - height[i];
        }
        return result;
    }
}

思路2代码

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0){
            return 0;
        }
        int height_size = height.length;
        int[] leftMaxs = new int[height_size];
        int[] rightMaxs = new int[height_size];
        leftMaxs[0] = height[0];
        rightMaxs[height_size - 1] = height[height_size - 1];

        for(int i = 1; i < height_size; i++){
            leftMaxs[i] = Math.max(height[i], leftMaxs[i - 1]);
            rightMaxs[height_size - i - 1] = Math.max(height[height_size - i - 1], rightMaxs[height_size - i]);
        }
        int result = 0;
        for(int i = 1; i < height_size - 1; i++){
            result += Math.min(leftMaxs[i], rightMaxs[i]) - height[i];
        }
        return result;
    }
}

思路三代码

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3){
            return 0;
        }
        int result = 0;
        int left = 0;
        int right = height.length - 1;
        int maxRight = 0;
        int maxLeft = 0;
        while (left < right){
            if (height[left] < height[right]){
                if(maxLeft < height[left]){
                    maxLeft = height[left];
                }else{
                    result += maxLeft - height[left];
                }
                left++;
            }else{
                if(maxRight < height[right]){
                    maxRight = height[right];
                }else{
                    result += maxRight - height[right];
                }
                right --;
            }
        }
        return result;
    }
}

复杂度分析

思路1时间复杂度

$O(n^2)$

思路1空间复杂度

$O(1)$

思路2时间复杂度

$O(n)$

思路2空间复杂度

$O(n)$

思路3时间复杂度

$O(n)$

思路3空间复杂度

$O(1)$