Leetcode 239: Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/description/

Notes:

This question is labeled as a hard problem. Apparently, it means the linear time.

We need to do two things:

1): find the maximum of a sling window;

2): pop up the element when it is out of range;

In order to pop up one element in O(1), we need set or map like data structures. (Actually we need multiset considering there may be elements with the same value.) But the time complexity is O(N*logK) in this way. Since we need to sort the element inside the container, which requires (logK).

Since we only care about the maximum, or larger elements. We can consider to use a deque.

No, a deque cannot sort the elements automatically, but we can maintain a deque with a decreasing order. Why? since we only need to keep larger elements.

We also need to consider how to pop up the element of out of the k range. Since we move element by element, for each step, we just need to take care of nums[i-k]. If it is still in the container, it must be the first one and also the largest one in the container. Otherwise, it had been removed earlier.

So if it is the front of the deque, we just need to pop the front element. That is another reason we choose the deque structure.

The last question, why is it a linear time?

For each element, we put it in the container once. And we pop them out by most once. Thus it is less than O(2*N), or O(N).

See the code below:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq;
        for(int i=0; i<nums.size(); ++i) {
            if(dq.size() && dq.front() == i - k) dq.pop_front();
            while(dq.size() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
            if(i>=k-1) res.push_back(nums[dq.front()]);
        }
        return res;
    }
};