剑指offer 59-1 滑动窗口内的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

使用一个队列记录滑动窗口内的最大值.

队列的规则如下:

• 队列是严格降序排列
• 新来的元素从队尾依次向前比较, 直到找到自己的位置后, 将后面的元素都删除
• 如果滑动窗口丢失的元素是队首元素, 那么队列弹出队首元素

通过这样的方式, 保证了最大值队列始终不为空, 同时最大值一定是队首元素

或许有人会问, 规则(2) 中最坏情况是每次的插入元素是升序, 导致时间复杂度N2? 不然, 如果是升序排列, 那么每次新增的元素都会将queue.size()变为1, 那么时间复杂度就降为了常数量

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    *returnSize = 0;
    if(!nums || numsSize ==0) return NULL;
    if(k == 0) return  NULL;

    *returnSize = numsSize - k + 1;
    int *ret = malloc(sizeof(int) * (*returnSize));
    int reti = 0;

    //一个队列, 记录窗口内的最大值, 如果新来的比队列所有的都大, 就清空队列; 否则放入
    int* maxqueue = malloc(sizeof(int) * k);
    int qhead = 0, qi = qhead;

    //第一次
    maxqueue[qi%k] = nums[0];
    int i = 1;
    while(i < k)
    {
        if(nums[i] > maxqueue[qhead%k])
        {
            maxqueue[qhead%k] = nums[i];
            qi = qhead;
            i++;
            continue;
        }
        //从队尾向前找适合自己的位置,并把之后的都删掉
        while(nums[i] > maxqueue[qi%k])
        {
            qi--;
        }
        qi++;
        maxqueue[qi%k] = nums[i];
        i++;
    }
    ret[reti++] = maxqueue[qhead%k];
    for(i = k; i < numsSize ; i++)
    {
        //最大的出队了
        if(nums[i - k] == maxqueue[qhead%k])
        {
            qhead++;
        }

        //如果新增来的最大
        if(nums[i] > maxqueue[qhead%k])
        {
            maxqueue[qhead%k] = nums[i];
            qi = qhead;
        }
        //新来的元素从队尾开始找自己的位置, 并把之后的都删掉
        else
        {
            while(nums[i] > maxqueue[qi%k])
            {
                qi--;
            }
            qi++;
            maxqueue[qi%k] = nums[i];
        } 
        
         ret[reti++] = maxqueue[qhead%k];   
        
    }
    return ret;
}

时间复杂度: N
空间复杂度: K