C++ O(N) solution without deque


  • 0
    E

    Some explanations: the idea is to find k-1 max values each time until reaches the end. Start from the beginning, we want to find the max values in windows (0,k-1), (1,k), ..., (k-2, 2k-3). To do this, we can find the max values in windows starting from k-1 with increasing window size from 1 to k-2: (k-1,k-1), (k-1,k), ..., (k-1,2k-3); and max values in windows ending at k-2 with increasing windows size from 1 to k-2:(k-2,k-2), (k-3,k-2), ..., (0,k-2). Both of them can be easily achieved in one pass. Then max(0,k-1) = max(max(0,k-2), max(k-1,k-1)), max(1,k) = max(max(1,k-2), max(k-1,k)), ..., max(k-2,2k-3) = max(max(k-2,k-2), max(k-1,2k-3)). So it takes 3(k-1) times to compute k-1 max values. Therefore the time complexity is 3n, the running time on OJ is around 80ms to 90ms.

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> result;
            int n = nums.size();
            if(n == 0 || k == 0) return result;
            if(k == 1) return nums;
            
            int start = 0;
            int forwardMax[k-1];
            int backwardMax[k-1];
            while(start + (k-1) < n) {
                int forwardStart = start + k-1;
                int backwardStart = start + k-2;
                forwardMax[0] = nums[forwardStart];
                backwardMax[0] = nums[backwardStart];
                int forwardLength = min(k-1, n-forwardStart);
                for(int i = 1; i < forwardLength; i++) {
                    forwardMax[i] = max(nums[forwardStart+i], forwardMax[i-1]);
                }
                for(int i = 1; i < k-1; i++) {
                    backwardMax[i] = max(nums[backwardStart-i], backwardMax[i-1]);
                }
                for(int i = 0; i < forwardLength; i++) {
                    result.push_back(max(backwardMax[k-2-i], forwardMax[i]));
                }
                start += k-1;
            }
            return result;
        }
    };

Log in to reply
 

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