1、前言

题目描述

2、思路

此题与《盛最多水的容器》的区别在于，《盛最多水的容器》可以直接根据两边的索引求值，然后分别进行递归。这道题不能直接求值（能不能递归不知道哈），只能针对每一个列能装多少水进行计算，所以最重要的是计算出每个列能装多少水。

对于为止 i 能装的水的格数：

water[i] = min(
               # 左边最高的柱子
               max(height[0..i]),  
               # 右边最高的柱子
               max(height[i..end]) 
            ) - height[i]

3、代码

1⃣️ 暴力解法：

public int trap(int[] height) {
        int res = 0, n = height.length;
        for(int i = 1; i < n - 1; i++){
            int lmax = 0, rmax = 0;

            for(int j = i; j >= 0; j--){
                if(height[j] > lmax){
                    lmax = height[j];
                }
            }

            for(int j = i; j < n; j++){
                if(height[j] > rmax){
                    rmax = height[j];
                }
            }

            res += Math.min(lmax, rmax) - height[i];
        }

        return res;
    }

2⃣️ 使用备忘录

class Solution {
    public long maxWater (int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }

        int n = arr.length;
        int[] leftMemo = new int[n];
        int lMax = arr[0];
        for(int i = 0; i < n; i++){
            lMax = Math.max(lMax, arr[i]);
            leftMemo[i] = lMax;
        }

        int[] rightMemo = new int[n];
        int rMax = arr[n - 1];
        for(int i = n - 1; i >= 0; i--){
            rMax = Math.max(rMax, arr[i]);
            rightMemo[i] = rMax;
        }

        int res = 0;
        for(int i = 0; i < n; i++){
            res += Math.min(leftMemo[i], rightMemo[i]) - arr[i];
        }

        return res;
    }
}