Solutions in C++, read it and get hold of it


  • 3

    Solutions

    The solution here is quite direct, we have to control a sliding window and in each window we have to retrieve the local maximum as efficiently as possible.

    Selection

    Naturally, the first choice is to control a sliding window using a pair of index and in each window we select the maximum and store it; this naive solution is enclosed below.

    class Solution {
    private:
        int getMax(vector<int>& nums, int begin, int end)
        {
            int maxNum = nums[begin];
            for(int i = begin+1; i <= end; ++i) maxNum = max(maxNum, nums[i]);
            return maxNum;
        }
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) 
        {
            vector<int> v;
            for(int i = 0; i < nums.size(); ++i)
                if(i >= k-1) v.push_back(getMax(nums, i-k+1, i));
            return v;
        }
    };
    

    Set

    But quite directly, it's not efficient in selecting the maximum whose time complexity is O(nk). So we can adopt set which will automatically sort the numbers in O(klogk) and we can also keep the sliding window and easily retrieve the maximum in O(logk) which can be good enough here O(nlogk+klogk), which is O(nlogk) then. But here are some problems we need to consider:

    • how to handle it when several same numbers in the same sliding window - multiset then is needed;
    • when constraining the sliding window we cannot simply remove the (i-k)th number now which in multiset this operation will remove all the same numbers, so we have to find it first and then remove it by the iterator.
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
    	int size = nums.size();
    	vector<int> v;
    	if(size==0 || size<k) return v;
    	multiset<int> window;
    	for(int i = 0; i < size; ++i)
    	{
    		if(i >= k) 
    		{
    			auto iter = window.find(nums[i-k]);
    			window.erase(iter);
    		}
    		window.insert(nums[i]);
    		if(i >= k-1) v.push_back(*window.rbegin());
    	}
    	return v;
    }
    

    Array

    But actually we can do better. We can just use an array (as a window storing index to limit the range) to control the sliding window.

    But how big this window array should be?

    • since the numbers will come in and go out as the sliding window moves forward only once, so the maximal size of the window array is the same as the number array;
    • we can use two pointers begin and end to control the range here: deleting the (i-k)th number can be simply done by moving the begin forward; adding another number, just move the end backward;

    But how can we retrieve the maximal number within the window quickly? Via removing the invalid numbers (numbers without potential to be the maximal in the current window) from the window to retain the potential ones.

    • each time before we append another number we compare the current with the last of the window and if the last in the window is smaller, we just remove it by end-- (moving backward the end pointer) and then we append the current number to the window
    • then the maximum of the current window is nums[window[begin]].

    Why the maximum is then the number pointed by window[begin]?

    • since each time before we inserting a new number we will remove the less just before the current so the first number of the window will always be the biggest of the current window (if it's not, suppose the second then is the biggest, then when we inserting the second, the first will be removed, contradiction here);

    Still it's not over yet.

    • when we retaining the sliding window we cannot just move the begin pointer forward as before since the index of the begin can be replaced after removing and appending operations, so the checking condition should now be checking the index directly window[begin]==i-k, if this is true then remove it by begin++;

    How about not removing from the last, instead removing from the begin?

    • actually this cannot do, if the first of the window is big enough then all the rest of the window can be volatile, out of control and once the biggest removed as the window moves forward then the window will be unpredictable and the maximum again can not be retrieved easily.

    In a word, the current solution is taking up O(n) space and costing O(n) time, which is the best solution so far. Still choosing array instead of deque is a choice for better performance.

    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
    	vector<int> v;
    	int size = nums.size();
    	if(size==0 || size<k) return v;
    	int queue[size]{0};
    	int begin = 0, end = -1;
    	for(int i = 0; i < size; ++i)
    	{
    		if(end-begin>-1 && queue[begin]==i-k) begin++;
    		while(end-begin>-1 && nums[queue[end]]<nums[i]) end--;
    		queue[++end] = i;
    		if(i >= k-1) v.push_back(nums[queue[begin]]);
    	}
    	return v;
    }
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    S

    Since you are using an array approach, and the array from begin to end is always sorted, you could find the insertion point using binary search, then calculate the new end from your insertion point. It does more good for large k. However, in every worst case scenario for linear search, in the next round the queue only has one item. Linear search has the benefit of O(1) test vs O(lg(k)) when just appending to the list. I'm struggling to decide which would be better, but if the complexity isn't much, adding binary search might eek out a little more performance.


  • 0

    @sganje
    Perhaps you can show us the code or at least some pseudo code to present your idea, thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.