C++ without queue and one of the fastest pure c


  • 0
    N
    1. Using two int to mark the current max value(max) in window and the pointer of this value(pointer);
    2. if the pointer is between the [i,i+k), we need to campare the last element ( nums[i+k-1]) with the max value only;
    3. if not; we need to find the max value between [i,i+k) and remember the pointer ;
    • IN WORST ( from big to small): it costs (n-k)*k times;
    • IN BEST(sorted): it costs n times;

    with O(n) time and O(1) space; need not

    for cpp code (about 63 ms)

    class Solution
    {
      public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
            vector<int> ans;
            if (!k)
            {
                return ans;
            }
            int max = nums[0], mark = -k;
            for (int len = nums.size() - k, i = 0, j; i <= len; ++i)
            {
                if (mark < i)
                {// out of box [i,i+k) => remark the max value;
                    for (max = nums[i], mark = i, j = i + 1; j < k + i; ++j)
                    {
                        if (max < nums[j])
                        {//switch max value
                            max = nums[j];
                            mark = j;
                        }
                    }
                }
                else if (nums[i + k - 1] >= max) // the mark point is in the [i,i+k) => just compare the last element
                {// swith max element
                    mark = i + k - 1;
                    max = nums[i + k - 1];
                }
    
                ans.push_back(max);
            }
            return ans;
        }
    };
    

    for the c code (29 ms)

    int *maxSlidingWindow(int *nums, int numsSize, int k, int *returnSize)
    {
        *returnSize = k ? numsSize - k + 1 : 0;
        int *ans = malloc(*returnSize * sizeof(int));
        for (int i = 0, j, max = INT_MIN, mark = -1; i < *returnSize; ++i)
        {
            if (mark < i)
            { // out or box [i, i+k) => remark
                for (max = nums[i], mark = i, j = i + 1; j < k + i; ++j)
                {
                    if (max < nums[j])
                    {
                        max = nums[j];
                        mark = j;
                    }
                }
            }
            else if (nums[i + k - 1] >= max) // in [i,i+k) => just compare the last one;
            {
                mark = i + k - 1;
                max = nums[i + k - 1];
            }
            ans[i] = max;
        }
        return ans;
    }
    

Log in to reply
 

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