LeetCode-Trapping Rain Water-下雨积水-单调队列应用

浏览数：84 / 时间：2015年06月11日

https://oj.leetcode.com/problems/trapping-rain-water/

这道题使用单调队列能够O(n)时间解决。维护一个降序排列的单调队列。如果Ai>A[que.front]就说明能够使用que.front作为顶部计算一次积水。

当从0-n时，须注意队列中还有元素。需要反向再执行一次单调队列。但是只需要到之前队列的front的位置即可。

class Solution {
public:
    int trap(int A[], int n) {
        if (n==0) return 0;
        queue <int> que;
        que.push(0);
        int res=0;
        for (int i=1;i<n;i++){
            int cur=A[i];
            int t=A[que.front()];
            if (cur<t) que.push(i);
            else{
                while(!que.empty()){
                    res+=t-A[que.front()];
                    que.pop();
                }
                que.push(i);
            }
        }
        if (que.empty()) return res;
        int m=que.front();
        while(!que.empty()) que.pop();
        que.push(n-1);
        for (int i=n-2;i>=m;i--){
            int cur=A[i];
            int t=A[que.front()];
            if (cur<t) que.push(i);
            else{
                while(!que.empty()){
                    res+=t-A[que.front()];
                    que.pop();
                }
                que.push(i);
            }
        }
        return res;
    }
};