接雨水问题的高效解法：从暴力到双指针的优化实践

输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解释: 可以接 6 个单位的雨水

高度图:     [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
位置:        0  1  2  3  4  5  6  7  8  9  10 11
            
接水量:     [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]
总接水量: 6

public int trap(int[] height) {
    int n = height.length;
    int result = 0;
    
    for (int i = 1; i < n - 1; i++) {
        int leftMax = 0, rightMax = 0;
        
        // 找左边最高
        for (int j = i; j >= 0; j--) {
            leftMax = Math.max(leftMax, height[j]);
        }
        
        // 找右边最高
        for (int j = i; j < n; j++) {
            rightMax = Math.max(rightMax, height[j]);
        }
        
        // 计算当前位置接水量
        result += Math.min(leftMax, rightMax) - height[i];
    }
    
    return result;
}

public int trapDP(int[] height) {
    int n = height.length;
    if (n == 0) return 0;
    
    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    
    // 从左到右计算 leftMax
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i-1], height[i]);
    }
    
    // 从右到左计算 rightMax
    rightMax[n-1] = height[n-1];
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i+1], height[i]);
    }
    
    // 计算接水量
    int result = 0;
    for (int i = 0; i < n; i++) {
        result += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    
    return result;
}

public int trapTwoPointer(int[] height) {
    int n = height.length;
    if (n == 0) return 0;
    
    int left = 0, right = n - 1;
    int leftMax = 0, rightMax = 0;
    int result = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            // 处理左指针
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                result += leftMax - height[left];
            }
            left++;
        } else {
            // 处理右指针
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                result += rightMax - height[right];
            }
            right--;
        }
    }
    
    return result;
}

初始状态: [0,1,0,2,1,0,1,3,2,1,2,1]
          ↑                          ↑
        left=0                    right=11
        leftMax=0                 rightMax=0
        result=0
 
步骤1: height[left]=0 < height[right]=1
      - leftMax = max(0, 0) = 0
      - result += 0 - 0 = 0
      - left++ → left=1
 
步骤2: height[left]=1 > height[right]=1 (相等，处理右指针)
      - rightMax = max(0, 1) = 1
      - result += 1 - 1 = 0
      - right-- → right=10
      
... 继续这个过程直到 left >= right

@Test
public void testTrappingRainWater() {
    TrappingRainWater solution = new TrappingRainWater();
    
    // 基础测试用例
    int[] height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    assertEquals(6, solution.trapTwoPointer(height1));
    
    // 边界情况
    int[] height2 = {};
    assertEquals(0, solution.trapTwoPointer(height2));
    
    int[] height3 = {5};
    assertEquals(0, solution.trapTwoPointer(height3));
    
    // 单调递增
    int[] height4 = {1,2,3,4,5};
    assertEquals(0, solution.trapTwoPointer(height4));
    
    // 单调递减
    int[] height5 = {5,4,3,2,1};
    assertEquals(0, solution.trapTwoPointer(height5));
    
    // 复杂地形
    int[] height6 = {5,2,1,2,1,5};
    assertEquals(14, solution.trapTwoPointer(height6));
}

// TRAE IDE 会自动提示 Math 类的方法
result += Math.min(leftMax, rightMax) - height[i];

// TRAE IDE 会提示：确保数组索引在有效范围内
while (left < right) {
    // 算法逻辑
}