Sliding Window Maximum

• monotonic stack solution
• Time : $O(n)$
• Space : $O(B)$

vector<int> Solution::slidingMaximum(const vector<int> &A, int B) {
    deque<int> st;
    vector<int> res;
    for(int i = 0; i < A.size(); i++) {
        while(!st.empty() and A[st.back()] <= A[i]) st.pop_back();
        st.push_back(i);
        while(!st.empty() and st.front() <= i - B) st.pop_front();
        if(i >= B - 1) res.push_back(A[st.front()]);
    }
    return res;
}

• heap solution
• Time : $O(nlogn)$
• Space : $O(n)$

vector<int> Solution::slidingMaximum(const vector<int> &A, int B) {
    priority_queue<int> window, cut;
    vector<int> res;
    for(int i = 0; i < A.size(); i++) {
        if(i >= B) cut.push(A[i-B]);
        window.push(A[i]);
        while(!cut.empty() and cut.top() == window.top()) {
            cut.pop();
            window.pop();
        }
        if(i >= B - 1) res.push_back(window.top());
    }
    return res;
}