首页 > 代码库 > LeetCode-Trapping Rain Water-下雨积水-单调队列应用

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

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;    }};

 

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