# My c++ solution with O(n*logk)

• If k=0, just return empty vector;

If k=1, return vector nums;

If k=2, the ith element of the result should be max(nums[i], nums[i+1]);

If we have got the result of k-1, so the ith element of the result should be max(result[i], nums[i+k-1]).

Then we will get the most simple solution:

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(k==0) return (vector<int>());
vector<int> result = nums;
int nums_size = nums.size();
for(int i=1; i<k; ++i){
for(int j=0; j<nums_size-i; ++j){
result[j] = max(result[j], nums[j+i]);
}
}

result.resize(nums_size-k+1);

return result;
}
};
``````

But in the above implementation, we have do much more computation.
Suppose if k=4, and we have the result of k=2, then the ith element of the result is max(result[i], result[i+2]). In the same way, we could get all the solutions of k=pow(2, n), (n=0, 1, 2, 3,...) with much less computation.

And k could be represented with binary numbers, k = c0.pow(2, 0) + c1.pow(2, 1) + ... (ci = 0,1). The final result could be calculated with pow(2, ci), for all ci=1 in k.

So the better solution arrives.
nums will be used to store the result for offset = pow(2, i); i=0,1,2,3.
result will be used to store the temp result.
For all the offset <= k, if (k&offset != 0), we should recalculate the result, then the ith element of the result should be max(nums[i], result[i+offset]).

The code:

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
int nums_size = nums.size();
int offset = 1;

while(k >= offset){
if((k&offset) != 0){
if(result.size() == 0){
result = nums;
}else{
for(int i=0; i<nums_size-offset;++i){
result[i] = max(result[i+offset], nums[i]);
}
}
}

if(k >= (offset<<1)){
for(int i=0; i<nums_size-offset; ++i){
nums[i] = max(nums[i], nums[i+offset]);
}
}

offset <<= 1;
}

if(k != 0)
result.resize(nums_size-k+1);

return result;
}
};``````

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