Leetcode 42.接雨水(栈)
程序员文章站
2024-01-20 09:41:16
...
class Solution{
public:
int trap(vector<int> &h)
{
int ans = 0;
int current = 0;
stack<int> st;
while(current < h.size())
{
while(!st.empty() && h[current] > h[st.top()])
{
int top = st.top();//2
st.pop();
if(st.empty()) break;
int distance = current - st.top() - 1;
int bound_h = min(height[current],h[st.top()]) - h[top];
ans += distance * bound_h;
}
st.push(current++);
}
return ans;
}
};