42 接雨水

题目

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

示例 1：

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

代码与解析

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int lmax = 0, rmax = 0;
        int l = 0, r = n - 1;
        int ans = 0;

        // 使用双指针法，移动左右指针，计算能够接的雨水量
        while(l < r) {
            if(height[l] < height[r]) {
                // 左侧高度较小，判断当前位置能否接雨水
                if(height[l] >= lmax) {
                    lmax = height[l]; // 更新左侧最大高度
                } else {
                    ans += (lmax - height[l]); // 计算当前位置能接的雨水量
                }
                l++; // 左指针右移
            } else {
                // 右侧高度较小，判断当前位置能否接雨水
                if(height[r] >= rmax) {
                    rmax = height[r]; // 更新右侧最大高度
                } else {
                    ans += (rmax - height[r]); // 计算当前位置能接的雨水量
                }
                r--; // 右指针左移
            }
        }
        return ans;
    }
}

怎么能想到这个方法，这种双指针法的思路通常需要具备对问题的一定直觉和灵活性。尝试从两个方向靠拢，同时记录下某种状态（比如左右两侧的最大高度）是这种问题常见的思路。练习和熟悉这类问题，逐渐就能形成一种思维模式，能够更快地发现这类问题的解决方法