Short C++ O(N)


  • 0
    I

    Here is a c++ O(n) code. Using deque you also delete from the back of a "queue" in o(1). deque is a bi-directional queue. Probably, all O(n) solutions are using this data structure or something similar.

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> res;
            deque<int> maxdq;
            for(int i = 0; i < nums.size(); i++){
                while(!maxdq.empty() && maxdq.back() < nums[i]) maxdq.pop_back();
                maxdq.push_back(nums[i]);
                if(i>=k && maxdq.front() == nums[i-k]) maxdq.pop_front();
                if(i >= k-1) res.push_back(maxdq.front());
            }
            return res;
        }
    };
    

Log in to reply
 

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