[LintCode/LeetCode] Sliding Window Maximum

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Example

For array [1, 2, 7, 7, 8], moving window size k = 3. return[7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8] , return the maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Challenge

o(n) time and O(k) memory

Analysis: Maintain a deque, which saves the indexes of a subset of k-sorted array, so that the front index is always the index of the biggest element in the sliding window.

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The maximum number inside the window at each moving.
     */
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        vector<int> res;
        if(nums.size() == 0 || k == 0)
            return res;
        deque<int> Q;
        for(int i=0;i<k;i++)
        {
            while(!Q.empty()&&nums[i]>=nums[Q.back()])
                Q.pop_back();
            Q.push_back(i);
        }
        res.push_back(nums[Q.front()]);
        
        for(int i=k;i<nums.size();i++)
        {
            while(!Q.empty()&&nums[i]>=nums[Q.back()])
                Q.pop_back();
            while(!Q.empty()&& i-Q.front()>=k)
                Q.pop_front();
            Q.push_back(i);
            res.push_back(nums[Q.front()]);
        }
        return res;
    }
};