单调栈

时间复杂度 $O(n)$

template <class T1, class T2>
class dd_stack {
public:
    void lmax(vector<T1> &v, vector<T2> &ans) { // 左边第一个比它大
        int n = v.size() - 1;
        stack<int> sk;
        fore(i, 1, n) {
            while (!sk.empty() && v[sk.top()] <= v[i])
                sk.pop();
            ans[i] = sk.empty() ? 0 : sk.top();
            sk.push(i);
        }
    }
    void rmax(vector<T1> &v, vector<T2> &ans) { // 右边第一个比它大
        int n = v.size() - 1;
        stack<int> sk;
        rfoe(i, n, 1) {
            while (!sk.empty() && v[sk.top()] <= v[i])
                sk.pop();
            ans[i] = sk.empty() ? n + 1 : sk.top();
            sk.push(i);
        }
    }
    void lmin(vector<T1> &v, vector<T2> &ans) { // 左边第一个比它小
        int n = v.size() - 1;
        stack<int> sk;
        fore(i, 1, n) {
            while (!sk.empty() && v[sk.top()] >= v[i])
                sk.pop();
            ans[i] = sk.empty() ? 0 : sk.top();
            sk.push(i);
        }
    }
    void rmin(vector<T1> &v, vector<T2> &ans) { // 右边第一个比它小
        int n = v.size() - 1;
        stack<int> sk;
        rfoe(i, n, 1) {
            while (!sk.empty() && v[sk.top()] >= v[i])
                sk.pop();
            ans[i] = sk.empty() ? n + 1 : sk.top();
            sk.push(i);
        }
    }
};

单调队列

时间复杂度 $O(n)$

template <class T>
class dd_deque {
public:
    void lmin(vector<T> &v, int k) { // 滑动窗口最小值
        int n = v.size() - 1;
        deque<int> dq;
        fore(i, 1, n) {
            while (!dq.empty() && v[i] <= v[dq.back()])
                dq.pop_back();
            dq.push_back(i);
            if (i - dq.front() >= k)
                dq.pop_front();
            if (i >= k)
                cout << v[dq.front()] << " \n"[i == n];
        }
    }
    void lmax(vector<T> &v, int k) { // 滑动窗口最大值
        int n = v.size() - 1;
        deque<int> dq;
        fore(i, 1, n) {
            while (!dq.empty() && v[i] >= v[dq.back()])
                dq.pop_back();
            dq.push_back(i);
            if (i - dq.front() >= k)
                dq.pop_front();
            if (i >= k)
                cout << v[dq.front()] << " \n"[i == n];
        }
    }
};