LeetCode42. 接雨水(java)
阅读原文时间:2023年07月10日阅读:3

给定 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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/trapping-rain-water

思路一:按行求解

这是我最开始想到的一个解法,虽然提交后挂掉了,但也通过了314 / 315 个通过测试用例。就是先求高度为 1 的水,再求高度为 2 的水,再求高度为 3 的水。(代码做了详细注释)

public class A42 {
    public static void main(String[] args) {
        int[] str = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(str));
    }

    public static int trap(int[] height) {
        int count=0;
        //找到数组最大值n,确定需要按行求需要求几行
        int n=0;
        for (int i = 0; i < height.length; i++) {
            if (height[i]>n) n=height[i];
        }
        //计算每行能够存储的数据的值,根据最大值高度作为循环次数
        for (int i = 0; i < n; i++) {
            //计算第0行
            count += getNum(height);
            //每次将所有数据都减1,相当于第一行变成第零行
            for (int j = 0; j < height.length; j++) {
                height[j]=height[j]-1;
            }
        }
        return count;
    }

    //计算第0行能够存储的水的数量
    public static int getNum(int[] arr){
        //a标记第一个大于0的数据,b标记最后一个大于0的数据
        int a=0,b=arr.length;
        //num标记水量
        int num=0;
        //找到a的值
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>=1){
                a=i;
                break;
            }
        }
        //找到b的值
        for (int i = arr.length-1; i >= 0; i--) {
            if (arr[i]>=1){
                b=i;
                break;
            }
        }
        //判断a-b之间小于1的即为能够存储一格水的
        for (int i=a;i<=b;i++){
            if (arr[i]<=0) num++;
        }
        return num;
    }
}

思路二:按列求解

成功AC的做法。找到数组中最大值分别计算左边和右边能够存储的雨水。以下图为例,a为标记位置向右检索找到比a大于或等于的数据即b,将总数据加上(b-a-1) *a的高度,再减去ab之间的高度。b->c就是(7-3-1) *2-1-0-1=4.

public class A42Two {
    public static void main(String[] args) {
        int[] str = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(str));
    }

    public static int trap(int[] height) {
        int count=0;
        //找到最大值,以及下标
        int max = 0;
        int max_index = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] >= max) {
                max = height[i];
                max_index = i;
            }
        }
        //左侧从第一个值开始找大于等于他的位置
        int start = 0;
        for (int i = 1; i <= max_index; i++) {
            if (height[i]>=height[start]){
                count += height[start]*(i-start-1);
                for (int j = start+1; j < i; j++) {
                    count-=height[j];
                }
                start=i;
            }
        }
        //右侧从第一个值开始找大于等于他的位置
        int end = height.length-1;
        for (int i = end-1; i >=max_index ; i--) {
            if (height[i]>=height[end]){
                count += height[end]*(end-i-1);
                for (int j = i+1; j < end; j++) {
                    count-=height[j];
                }
                end=i;
            }
        }
        return count;
    }
}