C++ solution using deque, with simple comment


  • 3
    L
     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        const int size_n =  nums.size();
       vector<int> result;
        if (k == 0 || size_n == 0) return result;
        deque<int> win;
        for (int i = 0; i < size_n; i++) {
            // delete the first one if it not belongs to this window
            if (!win.empty() && win.front() == i-k)
                  win.pop_front();
            // find the first element in win which less than nums[i]
            auto it = win.begin();
            for (; it < win.end(); it++) {
                if (nums[i] >= nums[*it]) break;
            }
            // delete all the elements less than cur nums[i], then push_back(nums[i])
            win.erase(it, win.end());
            win.push_back(i);
            // the first element in the queue is the max one for cur window
            if (i >= k-1)
                result.push_back(nums[win.front()]);
        }
        return result;
    }

Log in to reply
 

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