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


  • 0
    C

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

Log in to reply
 

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