Clean C++ 62ms solution beats 98.22%, no extra space


  • 0
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int>res;
            if(nums.size() == 0) return res;
            int start = 0;
            int end = k - 1;
            int maxIndex = findMax(nums, start, end);
            for(;end < nums.size(); start++, end++){
                if(nums[end] > nums[maxIndex]) maxIndex = end;
                if(start > maxIndex) maxIndex = findMax(nums, start, end);
                res.push_back(nums[maxIndex]);
            }
            return res;
        }
        
        int findMax(vector<int>& nums, int start, int end){
            int maxIndex = start;
            for(int i = start + 1; i <= end; i++)
                if(nums[i] > nums[maxIndex]) maxIndex = i;
            return maxIndex;
        }
    

    Hard to define its time complexity, if only consider findMax function itself, it's O(k), and main function takes O(n), we can say it's O(nk), but actually findMax function is not always get called per n, so in average it takes O(1), then in total it becomes O(n). Let me know what do you think.


Log in to reply
 

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