239.sliding-window-maximum.cpp

/*
 * @lc app=leetcode id=239 lang=cpp
 *
 * [239] Sliding Window Maximum
 *
 * https://leetcode.com/problems/sliding-window-maximum/description/
 *
 * algorithms
 * Hard (37.33%)
 * Total Accepted:    144K
 * Total Submissions: 385K
 * Testcase Example:  '[1,3,-1,-3,5,3,6,7]\n3'
 *
 * Given an array nums, there is a sliding window of size k which is moving
 * from the very left of the array to the very right. You can only see the k
 * numbers in the window. Each time the sliding window moves right by one
 * position. Return the max sliding window.
 * 
 * Example:
 * 
 * 
 * Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
 * Output: [3,3,5,5,6,7] 
 * Explanation: 
 * 
 * Window position                Max
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 * ⁠1 [3  -1  -3] 5  3  6  7       3
 * ⁠1  3 [-1  -3  5] 3  6  7       5
 * ⁠1  3  -1 [-3  5  3] 6  7       5
 * ⁠1  3  -1  -3 [5  3  6] 7       6
 * ⁠1  3  -1  -3  5 [3  6  7]      7
 * 
 * 
 * Note: 
 * You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty
 * array.
 * 
 * Follow up:
 * Could you solve it in linear time?
 */
#if 1 //96.29% runtime
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        if(!nums.size() || !k){
            return result;
        }
        if(k == 1){
            return nums;
        }
        result.reserve(nums.size() - k + 1);
        int max = nums[0];
        for(int i = 0; i < k; ++i){
            if(max < nums[i]){
                max = nums[i];
            }
        }
        result.push_back(max);

        for(int i = k; i < nums.size(); ++i){
            if(nums[i] > max){
                max = nums[i];
            }
            else if(nums[i-k] == max){
                max = nums[i-k+1];
                for(int j = i-k+1; j <= i; ++j){
                    if(nums[j] > max){
                        max = nums[j];
                    }
                }
            }
            result.push_back(max);
        }

        return result;
    }
};
#endif
#if 0 // 11.35% runtime
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        if(!nums.size() || !k){
            return result;
        }
        if(k == 1){
            return nums;
        }
        for(int i = 0; i < nums.size() - k + 1; ++i){
            int max = nums[i];
            for(int j = 0; j < k; ++j){
                if(nums[i + j] > max){
                    max = nums[i + j];
                }
            }
            result.push_back(max);
        }
        return result;
    }
};
#endif