LeetCode-[数组]-接雨水（三种解法）

题目描述

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

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

1. 暴力解法

O(N^2) 遍历数组，找出 i 左右两边的最大值，计算出 i 位置能存的水

public int trap(int[] height) {
          
   
        if (height == null || height.length < 3) {
          
   
            return 0;
        }
        int res = 0;
        for (int i = 1; i < height.length - 1; i++) {
          
   
            int leftMax = 0, rightMax = 0;  //定义在for里，因为每次都要更新
            for (int j = 0; j < i; j++) {
          
      //i 左边最大值
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int j = height.length - 1; j > i; j--) {
          
     //i 右边最大值
                rightMax = Math.max(rightMax, height[j]);
            }
            //与0比较：负数不要，说明i位置的柱子比左右两边都突出
            res += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
        }
        return res;
    }

2. 帮助数组

时复、空复：O(N) 对数组进行预处理，把数组i每个位置的左右两边的最大值都记录下来（从左往右和从右往左） 这样就剩下暴力法中每次都要遍历找最大值的功夫

public int trap(int[] height) {
          
   
        if (height == null || height.length < 3) {
          
   
            return 0;
        }
        int res = 0;
        int n = height.length - 2;  //头尾不用比较
        int[] leftMaxs = new int[n];
        int[] rightMaxs = new int[n];
        leftMaxs[0] = height[0];
        rightMaxs[n - 1] = height[n + 1];

        for (int i = 1; i < n; i++) {
          
     //生成 左——>右 的最大值数组
            leftMaxs[i] = Math.max(leftMaxs[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
          
      //生成 右——>左 的最大值数组。下标比较绕，但可以想明白
            rightMaxs[i] = Math.max(rightMaxs[i + 1], height[i + 2]);
        }
        for (int i = 1; i <= n; i++) {
          
     //遍历数组，帮助数组可以方便的确定 i 位置左右两边的最大值
            res += Math.max(0, Math.min(leftMaxs[i - 1], rightMaxs[i - 1]) - height[i]);
        }
        return res;
    }

3. 最优解——双指针

时间复杂度：O(N) 空间复杂度：O(1) 两个帮助数组可以用双指针+双变量优化，leftMax、rightMax分别记录 l 左右两边的最大值 在 l、r 遍历过程中，遇到更大值就更新 leftMax、rightMax

public int trap(int[] height) {
          
   
        if (height == null || height.length < 3) {
          
   
            return 0;
        }
        int res = 0;
        int l = 1, r = height.length - 2;  //双指针
        int leftMax = height[0], rightMax = height[height.length - 1];   //双变量
        while (l <= r) {
          
   
            if (leftMax <= rightMax) {
          
   
                res += Math.max(0, leftMax - height[l]);
                leftMax = Math.max(leftMax, height[l++]); //更新左边的最大值
            } else {
          
   
                res += Math.max(0, rightMax - height[r]);
                rightMax = Math.max(rightMax, height[r--]); //更新右边的最大值
            }
        }
        return res;
    }