LeetCode 42. 接雨水（双指针、单调栈）

示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

class Solution {
public:
    int trap(vector<int>& h) {
    	if(h.empty())
    		return 0;
        int i = 0, s = 0, n = h.size();
        int Lmax[n], Rmax[n];
        Lmax[0] = h[0];
        for(i = 1; i < n; ++i)
        	Lmax[i] = max(h[i],Lmax[i-1]);
        Rmax[n-1] = h[n-1];
        for(i = n-2; i >= 0; --i)
        	Rmax[i] = max(h[i],Rmax[i+1]);
        for(i = 1; i < n-1; ++i)//两边永远装不了水
        	s += min(Lmax[i],Rmax[i])-h[i];
        return s;
    }
};

class Solution {
public:
    int trap(vector<int>& h) {
    	if(h.empty())
    		return 0;
        int l = 0, r = h.size()-1, s = 0;
        int Lmax = 0, Rmax = 0;
        while(l < r)
        {
        	if(h[l] < h[r])//右边肯定有堵高墙
        	{
        		h[l] >= Lmax ? (Lmax = h[l]) : s += Lmax-h[l];
        		//我不是左边最高的，就能盛水
        		++l;
        	}
        	else//h[l] >= h[r], 左边肯定有堵高墙
        	{
        		h[r] >= Rmax ? (Rmax = h[r]) : s += Rmax-h[r];
        		//我不是右边最高的，就能盛水
        		--r;
        	}
        }
        return s;
    }
};

class Solution {
public:
    int trap(vector<int>& h) {
        if(h.empty())
            return 0;
        int s = 0, top, distance, height;
        stack<int> stk;
        for(int i = 0; i < h.size(); ++i)
        {
            while(!stk.empty() && h[i] > h[stk.top()])//当前墙高于左边的，违反递减
            {	//需要把中间高度比我小的处理掉，保持栈内单调递减
                top = stk.top();//左边的墙 位置记为top（待处理的）
                stk.pop();//删除之（处理掉）
                if(stk.empty())//top它没有左边围墙了
                    break;
                distance = i-stk.top()-1;//top左边还有墙
                height = min(h[i],h[stk.top()]) - h[top];
                //两边的最低高度（水高） - 自身高度（容器厚度）
                s += distance*height;
            }//处理完了，现在栈内是递减的了 或者 空
            stk.push(i);//递减的话会一直push进来（一个\斜坡，存不住水）
            //一旦不是斜坡了，进入上面的循环
        }
        return s;
    }
};