LeetCode 42: 接雨水

解答

这个题需要好好分析一下，自己的思路离单调栈的标准答案就一步之遥了，就是没想出来，最近有点颓md，

代码一：单调栈

主要分析一下为什么自己的思路大体方向是正确的，但就是差最后一步。

首先，分析出来只有凹槽结构才能接雨水，单调栈处理每个凹槽结构，这个没问题。

接下来，应该按照行计算，我前面按照行的思路思考，但是后面却按照列的思路累加凹槽，想着对每个凹槽确定左右界限，列累加，杂糅了单调栈和动规，越写越乱。没有想到到底是按行计算还是按列计算，导致后面越写越乱。 根本原因还是拿着单调栈往上硬套，应该先分析题目中的特点和性质，然后确定方法，这个我还差的很多。

接下来分析一下单调栈。模拟一下单调栈，当now > height[st.top()]时，now左边就形成了一个凹槽，然后相当于用水填平这个凹槽，一层一层填，eg：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st; // format: idx
        int now=0, ans=0;
        for(int i=0; i<height.size(); i++){
            now = height[i];
            if(st.empty()) st.push(i);
            else if( now < height[st.top()] ) st.push(i);
            else if( now == height[st.top()]){
                st.pop();
                st.push(i);
            }
            else{ // now > height[st.top()]
                while(now > height[st.top()]){
                    int h = height[st.top()];
                    int idx = st.top();
                    st.pop();
                    if(st.empty()) break;
                    // printf("%d %d\n", height[st.top()], st.top());
                    ans += (min(height[st.top()], now) - h) * (i-st.top()-1);
                }
                if(!st.empty() && now == height[st.top()]){
                    st.pop();
                    st.push(i);
                }
                st.push(i);
            }
        }
        return ans;
    }
};

代码二：动规

思路来源于双指针，按列计算，要一列一列累加，
最关键的是想明白怎么确定水平面高度，自己一开始将关注点放在了单调栈退栈的时刻，如何确定左侧对应的高度，杂糅了按列计算和按行计算。没有想到一个凹槽水平面是由两侧高度最大的列所确定。
动规的递推反而很简单

忘了的话再看一下代码随想录