题目理解：

能接到水的前提是：当前位置的柱子比左右两边的柱子矮，形成一个凹陷。  
打个比方，就像用木桶装水，水能装在桶里的前提是中间的地方低，两边的桶壁高。  
如果两边的桶壁都比中间高，水才能留下来；但如果有一边比中间低，水就直接流走了，装不了水。  
所以，只有左右两边的高度都高于中间的高度，才能在中间装水。

方法一---动态规划

首先，判断左侧柱子是否比当前柱子高；然后，判断右侧柱子是否比当前柱子高，最后，比较两侧柱子，取最小值，较矮柱子与当前位置的差值即为可以接到的雨水

代码思路：

1. 遍历数组，计算当前位置左边柱子的最高高度

2. 遍历数组，计算当前位置右边柱子的最高高度

3. 最后比较左右两边的最高高度，取较小值，减去当前位置的高度，得到当前位置能接的水量

4. 把每个位置的水量加起来，就是总共能接的雨水量

   class Solution {
   public:
       int trap(vector<int>& height) {
           int water =  0;
           vector<int> l_max(height.size());
           l_max[0] = height[0];
           //计算当前位置左边柱子的最高高度
           for(int i = 1; i < height.size(); i++){
               l_max[i] = max(l_max[i - 1], height[i]);
           }
           vector<int> r_max(height.size());
           r_max[height.size() - 1] = height[height.size() - 1];
           //计算当前位置右边柱子的最高高度
           for(int i = height.size() - 2; i >= 0; i--){
               r_max[i] = max(r_max[i + 1], height[i]);
           }
           for(int i = 0; i < height.size(); i++){
               water += min(l_max[i], r_max[i]) - height[i];
           }
           return water;
           
       }
   };

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

如果不再对从左（右）边看的最大值进行记录，是否可以将空间复杂度降为O(1)？

考虑通过维护双指针以及两个变量同时计算当前凹槽左边柱子和右边柱子的最高高度，寻找可以存水的凹槽

class Solution {
public:
    int trap(vector<int>& height) {
        int n =  height.size();
        int water =  0;
        
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        while(left < right){
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            //如果左侧柱子较矮，那么盛水量由左侧柱子决定
            //反之如果右侧柱子较矮，那么成水量就由右侧柱子决定
            if(leftMax < rightMax){
                water += leftMax - height[left];
                left++;
            }
            else{
                water += rightMax - height[right];
                right--;
            }
        }
        
        return water;
    }
};

方法二---单调递减栈（栈顶（栈的出口）到栈底是单调递减的）

借助栈找到每个凹陷位置的左边界，并确定当前凹陷的底部高度，从而确定当前位置能够接的水量，然后累加得到最终的雨水量

注意！栈中存放的是柱子的索引

代码思路：

• 遍历数组，使用一个栈保存尚未确定是否能够成为凹陷左边界的柱子索引

• 如果当前柱子的高度 height[i] 大于栈顶柱子的高度  height[stk.top()]，说明该位置可以形成凹陷，这时弹出栈顶元素，将其作为凹陷的底部height[top]，如果栈不为空，那么栈顶柱子弹出后新的栈顶柱子就是凹陷的左边界height[left]，当前柱子就是凹陷的右边界height[i]

• 这时，凹陷的宽度为即左右边界之间的距离减去当前柱子本身的宽度，即i - left - 1，凹陷的高度为左右两侧柱子中较矮柱子高度减去底部柱子的高度，即min(height[left], height[i]) - height[top]

• 将宽度和高度相乘得到每个凹陷的可以容纳的雨水量，将所有累加起来，就是总共能接的雨水量

class Solution {
public:
    int trap(vector<int>& height) {
        int water = 0;
        stack<int> stk;//用于寻找凹陷的左边界
        for(int i = 0; i < height.size(); ++i){
            while(!stk.empty() && height[i] > height[stk.top()]){
                int top = stk.top();//凹陷位置下标
                stk.pop();               
                //栈中元素为空说明目前没有可以构成凹陷的左边界，
                //因此跳过本次循环
                if(stk.empty()){
                    break;
                }
                int left = stk.top();//凹陷左边界下标

                //计算当前凹陷储水量
                int current_w = i - left - 1;
                int current_h = min(height[left], height[i]) - height[top];
                water += current_h * current_w;

            }
            stk.push(i);//将当前柱子下标压入栈中
            
        }
        return water;
        
    }
};

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