C++ using multiset - O(nlgK)


  • 0
    P

    This is a slower solution, but it's quite simple. When k is small, it's still linear (lgK is constant).

    #include <multiset>
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> result;
            if(k > 0 && nums.size() >= k) {
                multiset<int> window;
                for(int i = 0; i < k; ++i) {
                    window.insert(nums[i]);
                }
                result.push_back(*window.rbegin());
                for(int i = k; i < nums.size(); ++i) {
                    auto it = window.find(nums[i - k]);
                    window.erase(it);
                    window.insert(nums[i]);
                    result.push_back(*window.rbegin());
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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