[Leetcode] Sliding Window Maximum

Use deque to keep a decrease queue. Total run-time of O(n).

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        typedef pair<int, int> pii;
        deque<pii> dq;
        int n = nums.size();
        vector<int> ans;
        for(int i = 0; i < n; i++) {
            while(!dq.empty() && dq.back().first < nums[i]) dq.pop_back();
            dq.push_back(make_pair(nums[i], i));
            while(dq.front().second <= i - k) dq.pop_front();
            if (i >= k - 1) ans.push_back(dq.front().first);
        }
        return ans;
    }
};

Reference:
Sliding Window Minimum Implementations
Double ended queue