欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 42.接雨水(栈)

程序员文章站 2024-01-20 09:41:16
...

Leetcode 42.接雨水(栈)

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;
	}		
};