LeetCode 42. 接雨水（C++）实现

单调栈思想解决本题

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

解题思路：

直观想法

我们可以用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。 我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到ans 。

算法：

int trap(vector<int>& height)
{
          
   
	//ans保存雨水 cunrrent为当前位置
    int ans = 0, current = 0;
    //栈保存高度
    stack<int> st;
    	//遍历所有的块
    while (current < height.size()) {
          
   
    	//当栈为非空时  或者  当前块比栈顶高时，说明可以接住雨水
        while (!st.empty() && height[current] > height[st.top()]) {
          
   
        //top保存洼地位置
            int top = st.top();
            	//弹出洼地的位置
            st.pop();
            if (st.empty())
                break;
             //计算洼地宽度
            int distance = current - st.top() - 1;
            	// 洼地附近的最低边缘减去洼地高度
            int bounded_height = min(height[current], height[st.top()]) - height[top];
            	//加上一块洼地的水容量
            ans += distance * bounded_height;
        }
        //!st.empty() ||height[current] < height[st.top()]满足时入栈
        st.push(current++);
    }
    return ans;
}