单调栈的应用,以及拆分思想

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣上的一道题。

如果你想练习手写单调栈模版可以看看这篇文章单调栈模版-CSDN博客

当然这篇文章里我会使用STL里的stack。

试想一下，我们可以把题目中的数字具象化成一个个碗。

比如像这样

?

而21013这个大碗又可以分为两个小碗来计算

?

所以我们只需要找到它的底边和高即可。

维护一个单调递减的栈，当遇到stack.top()<a[i]时，每次取底边长cur=stack.top()，然后pop，然后再取l=stack.top(),ans=(std::min(a[i],a[l])-a[cur])*(i-l-1);这个式子可同时满足1.l=cur,此时ans+=0,2.l>cur，其中一个有效碗。

所以代码就是这样啦

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++)
        {
            while (!st.empty() && height[st.top()] < height[i])
            {
                int cur = st.top();
                st.pop();
                if (st.empty()) break;
                int l = st.top();
                int r = i;
                int h = min(height[r], height[l]) - height[cur];
                ans += (r - l - 1) * h;
            }
            st.push(i);
        }
        return ans;
    }
};