3 C++ Solutions


  • 15
    M
    1. O(NlogK)
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        if (k == 0) return result;
        multiset<int> w;
        for (int i = 0, n = (int)nums.size(); i < n; i++) {
            if (i >= k)
                w.erase(w.find(nums[i-k]));
            w.insert(nums[i]);
            if (i >= k-1)
                result.push_back(*w.rbegin());
        }
        return result;
    }
    
    2. O(NlogN)
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        if (k == 0) return result;
        priority_queue<pair<int, int>> w;
        for (int i = 0, n = (int)nums.size(); i < n; i++) {
            while (!w.empty() && w.top().second <= i-k)
                w.pop();
            w.push(make_pair(nums[i],i));
            if (i >= k-1)
                result.push_back(w.top().first);
        }
        return result;
    }
    
    3. O(N)
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        if (k == 0) return result;
        deque<int> w;
        for (int i = 0, n = (int)nums.size(); i < n; i++) {
            while (!w.empty() && w.front() <= i-k)
                w.pop_front();
            while (!w.empty() && nums[w.back()] <= nums[i])
                w.pop_back();
            w.push_back(i);
            if (i >= k-1)
                result.push_back(nums[w.front()]);
        }
        return result;
    }

  • 2
    T

    Another O(N) time & O(N) space in C++

    class Solution {
    public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        int n = nums.size();
        vector <int> res;
        
        if(n == 0)
            return res;
        if(k == 1)
            return nums;
        
        int left[n]; 
        int right[n]; 
        
        left[0] = nums[0];
        right[n - 1] = nums[n - 1];
        
        //max from left in the windows of k
        for(int i = 0;i < n;i++)
        {
            if(i % k == 0)
            left[i] = nums[i];
            else
            left[i] = std::max(nums[i],left[i - 1]);
        } 
        
        // max from right in the windows of k
        for(int i = n - 2;i >= 0;i--)
        {
            if(i % k == 0)
            right[i] = nums[i];
            else
            right[i] = std::max(nums[i],right[i + 1]);
        } 
        
        //overall maximum
        for(int i = 0; i <= n - k;i++)
        {
            res.push_back(std::max(right[i],left[i + k - 1]));
        }
        return res;
    }
    

    };


  • 0
    M

    this is such a brilliant solution with simplest data structure. how did you come about it?


  • 0
    Z

    For solution 1, there are two conditions we need to pay more attention.

    Firstly, set/multiset is based on RB Tree structure, so we can add/remove/getMaxValue in logN time(N is the size of our set), We can use 'iterator' to get its elements in sorted order.

    Secondly, cosidering there might be repeat in nums, we use multiset instead of set. To remove the element nums[i-k]: If we use "w.erase(nums[i-k])", we actually remove all the elements equal to nums[i-k], which will lead to failing; When we use "w.erase(w.find(nums[i-k]))" , since w.find(someValue) will return iterator of the first found element that equals to nums[i-k], so we actually delete one element once.

    Thanks for sharing.
    ...
    ...


  • 0
    Z

    For solution 2: we can use max_heap to get the maximum element of N numbers, and each time we insert a new element, it will take o(logN) time.

    There are one difference in this problem:
    We need the maximum element under the window of size k, so we need to remove a[i-k] in time, but it is pretty hard to imply by a priority_queue.
    ----To solve this problem, we decide not to remove the element directly....
    Since we need to get the maximum element at each position and the maximum element lies on the top of the priority_queue, before saving this value in our res, we have to check wether it's out of the range k first.

    ...

    ...


Log in to reply
 

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