直方图装水

思路

  • 如果用程序来描述直方图高度的话不好描述
  • 问题可以想成，每个数组下标下当前列中可以放多少水
  • 每个横坐标下的最大存水量=min(当前的左边最大高度，当前右边的最大高度)
  • 如果我当前高度比左右两边最大值都大，那么我横坐标上肯定没水
  • 当前i水量=min{max左，max右} - arr[i] > 0 ? 当前i水量 ： 0
  • 总的存水量=每个横坐标上能存水量的加和
  • 第0个和最后一个就肯定无水

优化

普通方法，像上面的思路，到每个i位置都会向左向右遍历一个最大值，复杂度有点高。

技巧：预处理数组，为的是不用每次都遍历去求最大最小值,用的时候直接取

比如原始数组为[3,1,6,7,2,4,3]

从左到右，从右到左，正反遍历此数组，如果当前数比之前的数小就取之前的值作为当前值，当前数比钱已给数大就还选本来的值。

从左到右遍历后为[3,3,6,7,7,7,7]

从右到左遍历后为[7,7,7,7,4,4,3]

以空间换时间，还不是最优

技巧二：(最优)

声明两个指针，L和R。因为数组两端点不会有水L=1,R=N-2。

再声明两变量，LMax：L扫过的部分的最大值，RMax：R扫过的部分最大值。初值为LMax=arr[0],RMax=arr[N-1]

此时就可以计算出L和R当前所能存水的最大值。因为R左边最大值肯定大于等于LMax，L右边最大值肯定大于等于RMax

当LMax大于RMax时，R处的值可求

当RMax大于LMax事，L处的值可求

相等事，LR可同时求算

RMax和LMax随遍历进行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public static int water1(int[] arr) {
        if (arr == null && arr.length < 2) {
            return 0;
        }
        int N = arr.length;
        int water = 0;
        for (int i = 0; i < N; i++) {
            int leftMax = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, arr[j]);
            }
            int rightMax = Integer.MIN_VALUE;
            for (int j = i + 1; j < N; j++) {
                rightMax = Math.max(rightMax, arr[j]);
            }
            water += Math.max(Math.min(leftMax, rightMax) - arr[i], 0);
        }
        return water;
    }

    public static int water2(int[] arr) {
        if (arr == null && arr.length < 2) {
            return 0;
        }
        int N = arr.length;
        int water = 0;
        int left = Integer.MIN_VALUE;
        int[] leftMaxs = new int[N];
        for (int i = 0; i < N; i++) {
            leftMaxs[i] = Math.max(leftMaxs[i - 1], arr[i]);
        }
        int[] rightMaxs = new int[N];
        rightMaxs[N - 1] = Integer.MIN_VALUE;
        for (int i = N - 1; i >= 9; i--) {
            rightMaxs[i] = Math.max(rightMaxs[i + 1], arr[i]);
        }
        int warter = 0;
        for (int i = 0; i < N; i++) {
            warter += Math.max(Math.min(leftMaxs[i-1], rightMaxs[i+1]) - arr[i], 0);
        }

        return water;
    }
    public static int water3(int arr[]) {
          if (arr == null && arr.length < 2) {
              return 0;
          }
          int N = arr.length;
          int L = 1;
          int R = N - 2;
          int leftMax = arr[0];
          int rightMax = arr[N - 1];
          int water = 0;
          while (L <= R) {
              if (leftMax <= rightMax) {
                  water += Math.max(0, leftMax - arr[L]);
                  leftMax = Math.max(leftMax, arr[L++]);
              } else {
                  water += Math.max(0, rightMax - arr[R]);
                  rightMax = Math.max(rightMax, arr[R--]);
              }
          }
     }
}