单调队列 Monotone Queue

即保证队列内元素单调性的队列。

通常用于滑动窗口的极值问题。

//// c version (min)
int q[maxn]; // the monotone values inside the window 
int p[maxn]; // the indices
int h = 0, t = 0;
for (int i = 0; i < n; i++) {
    // remove time-out 
    while (h < t && p[h] <= i - k) h++;
    // maintain queue (cs[i] is the current val, remove vals larger than it.)
    while (t >= 1 && xs[i] < q[t-1]) t--;
    p[t] = i;
    q[t++] = xs[i];
    // now q[h] is the min value in window (i-k, i]
    ...;
}

//// stl version (min)
vector<int> q; // store values
deque<int> p; // store enqueue time
for (int i = 0; i < n; i++) {
    while (!p.empty() && p.front() <= i - k) p.pop_front();
    while (!p.empty() && xs[i] < q[p.back()]) p.pop_back(); // < or <= is both OK.
    p.push_back(i);
    q.push_back(xs[i]);
    // q[p.front()] is the min value in window (i-k, i]
    ...;
}

//// stl version (max)
vector<int> q; // store values
deque<int> p; // store enqueue time
for (int i = 0; i < n; i++) {
    while (!p.empty() && p.front() <= i - k) p.pop_front();
    while (!p.empty() && xs[i] > q[p.back()]) p.pop_back(); // > or >= is both OK.
    p.push_back(i);
    q.push_back(xs[i]);
    // q[p.front()] is the min value in window (i-k, i]
    ...;
}

滑动窗口极值

裸模板\(O(N)\)：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // monotone queue
        vector<int> q;
        deque<int> p;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            while (!p.empty() && p.front() <= i - k) p.pop_front();
            while (!p.empty() && q[p.back()] <= nums[i]) p.pop_back();
            p.push_back(i);
            q.push_back(nums[i]);
            if (i >= k - 1) ans.push_back(q[p.front()]);
        }
        return ans;
    }
};

另一种形式（deque不维护时间，直接维护最值）

class Solution {
public:
    struct monoque{
        deque<int> que;
        void push(int n){
            while(!que.empty() && que.back()<n) que.pop_back();   
            que.push_back(n);
        }
        int getmax(){ return que.front(); }
        void pop(int n){ 
            if(que.front() == n) que.pop_front(); 
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int N = nums.size();
        vector<int> ans;
        monoque que;
        for(int i=0; i<N; i++){
            que.push(nums[i]);
            if(i>=k-1){
                ans.push_back(que.getmax());
                que.pop(nums[i-k+1]);
            }
        }
        return ans;
    }
};

使用Sparse Table的RMQ算法也可以\(O(N)\)。

Maximum value in queue

deque直接记录当前窗口的最值。

class MaxQueue {
public:

    queue<int> q;
    deque<int> p;

    MaxQueue() {}

    int max_value() {
        if (q.empty()) return -1;
        return p.front();
    }

    void push_back(int value) {
        q.push(value);
        while (!p.empty() && value > p.back()) p.pop_back(); // must be >, cannot use >=
        p.push_back(value);
    }

    int pop_front() {
        if (q.empty()) return -1;
        int x = q.front(); q.pop();
        if (x == p.front()) p.pop_front();
        return x;
    }
};

Maximum Sum Circular Subarray

前缀和&滑动窗口：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();

        // copy
        vector<int> AA;
        for (int i = 0; i < n; i++) AA.push_back(A[i]);
        for (int i = 0; i < n; i++) AA.push_back(A[i]);

        // cumsum
        vector<int> cs(2*n+1, 0);
        for (int i = 1; i <= 2 * n; i++) {
            cs[i] = cs[i - 1] + AA[i - 1];
        }

        vector<int> q; // store values
        deque<int> p; // store enqueue time
        q.push_back(0);
        p.push_back(0);

        int ans = -0x3f3f3f3f;
        for (int i = 1; i <= 2 * n; i++) {
            // maintain queue
            while (!p.empty() && p.front() < i - n) p.pop_front();
            // maintain ans
            ans = max(ans, cs[i] - q[p.front()]);
            // maintain queue
            while (!p.empty() && cs[i] < q[p.back()]) p.pop_back();
            p.push_back(i);
            q.push_back(cs[i]);
        }
        return ans;

    }
};

Kadane Twice：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        // kadane 1
        int ans = A[0];
        int dp = A[0];
        for (int i = 1; i < n; i++) {
            dp = max(dp + A[i], A[i]);
            ans = max(ans, dp);
        }
        // kadane 2 (if at least 3 elements)
        int ans2 = ans;
        if (n >= 3) {
            int s = 0;
            for (int i = 0; i < n; i++) s += A[i];
            ans2 = A[1];
            dp = A[1];
            for (int i = 2; i < n - 1; i++) {
                dp = min(dp + A[i], A[i]);
                ans2 = min(ans2, dp);
            }
            ans2 = s - ans2;
        }
        // final
        return max(ans, ans2);
    }
};

The next larger element (monotone stack)

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

倒序遍历+单调栈。\(O(n+m)\)时间复杂度。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // track next larger element for all pos in nums2
        unordered_map<int,int> hashmap;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!st.empty() && num >= st.top()) st.pop();
            hashmap[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        // retrieve answer
        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            res[i] = hashmap[nums1[i]];
        }
        return res;
    }
};