# C++ O(N) solution without deque

• 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;
}
};``````

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