13 lines concise and easy understand c++ solution, priority_queue with compare operator


  • 0
    A
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> res;
            if(nums.size() == 0) return res;
            int l = 0, r = 0;
            auto cmp = [](pair<int, int> a, pair<int, int> b) { return (a.first) < (b.first);};
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
            for(r = 0; r < k; r++) pq.push(make_pair(nums[r], r));
            res.push_back(pq.top().first);
            for(r = k; r < nums.size(); r++, l++) {
                pq.push(make_pair(nums[r], r));
                while(pq.size() > k && pq.top().second <= l) pq.pop();
                res.push_back(pq.top().first);
            }
            return res;
        }
    };
    

Log in to reply
 

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