接雨水问题：双指针与单调栈解法详解

1. 问题背景与核心挑战

接雨水问题(Leetcode第42题)是算法面试中的经典题目，考察对数组处理、边界条件和空间优化的综合把握。题目描述如下：给定n个非负整数表示的高度图，每个柱子的宽度为1，计算下雨后这个排列的柱子能接多少雨水。

实际场景可以想象成城市天际线，降雨时建筑物之间的凹陷区域会积水。例如输入[0,1,0,2,1,0,1,3,2,1,2,1]对应的雨水量为6。这个问题的难点在于：

• 需要同时考虑左右两侧的边界限制
• 不同解法在时间/空间复杂度上的取舍
• 边界条件的处理（如单调递减/递增序列）

2. 暴力解法与初步优化

2.1 直观的双层循环解法

最直接的思路是对每个柱子，分别向左向右找到最高柱子，取较小值减去当前高度：

cpp复制int trap(vector<int>& height) {
    int ans = 0;
    for (int i = 0; i < height.size(); i++) {
        int left_max = 0, right_max = 0;
        for (int j = i; j >= 0; j--) 
            left_max = max(left_max, height[j]);
        for (int j = i; j < height.size(); j++)
            right_max = max(right_max, height[j]);
        ans += min(left_max, right_max) - height[i];
    }
    return ans;
}

时间复杂度O(n²)，空间复杂度O(1)。这种解法在面试中仅作为起点，需要进一步优化。

2.2 预处理最大值数组

通过预先存储每个位置的左右最大值，可以避免重复计算：

cpp复制int trap(vector<int>& height) {
    if(height.empty()) return 0;
    int n = height.size();
    vector<int> left_max(n), right_max(n);
    
    left_max[