每日一题微信交流群可以点击右下角:合作转载->联系我,拉你入群。
题解: 单调栈
今日题目另一个名字就是接雨水,在面试中常考题目,单调栈的经典题型,在本题当中我们需要维护一个单调递减栈,当找到比栈顶元素大的点时,弹出栈顶,看此时栈是否空,要形成一个凹下去的样子,可以这样想象:凹这个字样子,分为三块,左边、中间凹下去点,右边。那么每次新来的点就是右边柱子,栈顶元素就是中间凹下去的点,左边柱子是距离栈顶的第一个元素,也就是栈顶下来就是这个左边元素。因此要计算面积,我们需要知道这三个点!
接下来,看代码实现部分,假期到了,每日一题我这边暂停了,假期来后,我们再继续刷~
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int n = height.size();
int ans = 0;
for (int i=0;i<n;i++) {
while (!st.empty() && height[st.top()]<=height[i]) {
int prev_height = st.top();
st.pop();
if (st.empty()) break;
int w = i - st.top() - 1;
int left_height = height[st.top()];
int h = min(left_height,height[i]) - height[prev_height];
ans += w*h;
}
st.push(i);
}
return ans;
}
};
本节完~