一. 题目

二. 思路

1. 左边界找最大右边界

• 若右边有>=当前值的，则找到右边第一个>=左边界的右边界。

• 若右边没有>=当前左边界的，则找到右边<左边界的最大的一个值。

• 要预处理rmax[i]:表示i右边的最大值，不含i

• 时间复杂度O(n)、空间复杂度O(n)

2. dp

3. 双指针

三. 代码

1. 左边界找最大右边界

class Solution
{
    static final int N = (int) 2e4 + 10;
    int[] rmax = new int[N];

    public int trap(int[] height)
    {
        int n = height.length;
        int maxv = height[n - 1];
        rmax[n - 1] = -1;
        for (int i = n - 2; i >= 0; --i)
        {
            rmax[i] = maxv;
            maxv = Math.max(maxv, height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; )
            if (rmax[i] >= height[i])//右边存在>=左边界的值
            {
                int lv = height[i++];//i要++, 因为刚开始height==lv
                while (i < n && height[i] < lv)//到达右边界停止
                    ans += lv - height[i++];
            } else
            {
                int j = i;
                while (j < n && rmax[i] == rmax[j]) ++j;//右边最大值停止
                while (++i < n && i < j) ans += height[j] - height[i];//i要先+，否则会hj-hi第一次计算是个负数
            }
        return ans;
    }
}

2. dp

class Solution
{
    static final int N = (int) 2e4 + 10;
    int[] lmax = new int[N], rmax = new int[N];

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

        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans += Math.min(lmax[i], rmax[i]) - height[i];
        return ans;
    }
}

3. 双指针

class Solution
{
    public int trap(int[] height)
    {
        int ans = 0;
        int lmax = 0, rmax = 0;
        for (int l = 0, r = height.length - 1; l < r; )//不用l==r是因为，最终相遇位置一定是一个最高点
        {
            lmax = Math.max(lmax, height[l]);
            rmax = Math.max(rmax, height[r]);//若h[l]<h[r]必有lmax<rmax，因为rmax至少为h[r]，且只有h[l]<h[r]时l才会右移
            if (height[l] < height[r]) ans += lmax - height[l++];
            else ans += rmax - height[r--];
        }
        return ans;
    }
}