博客

我们要求的是滑动窗口内的最大值，当然可以用暴力解法，遍历一遍数组，再遍历一遍0 到 k的位置，时间复杂度是 O(n*k);

我们这题用单调队列会好很多，当然也可以用优先队列，但是C语言并没有提供这种库函数，所以实现起来不如单调队列简单。

思路：

题目要求我们是求滑动窗口的最大值，所以我们只需要保证，队列的出口的第一个值，是该窗口的最大值，就OK了，我们只需要维护这个值。

第一步：

找到该窗口的最大值。

第二步：

将该值前面小于它的值全部出队，保证队列出口的值是该窗口的最大值。

注：这只是我们模拟的情况。

需要用到辅助数组；

第三步：

将该值保存下来。

下面贴出代码，会有注释帮助大家理解

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) 
{
    // 辅助数组
    int q[numsSize];
    int left = 0, right = 0; 


    for (int i = 0; i < k; i++)
    {
        // 将最大值始终保持在队列出口
        while (left < right && nums[i] < nums[q[right - 1]])
        {
            right--;
        }        

        q[right++] = i;
    }

    // 创建保存最大值的返回数组
    *returnsSize = 0;

    // 数组长度是 k移动到数组末尾的次数;
    int* ans = (int*)malloc(sizeof(int) * numsSize - k + 1);

    // 保存最大值
    ans[(*retuansSize)++] = nums[q[left]];
    

    for (int i = k; i < numsSize; i++)
    {
        while (left < right && nums[i] < nums[q[right - 1]])
        {
            right--;
        }
        

        q[right++] = i;

        // 跟着滑动窗口移动。 保证该窗口的最大值在队列出口处
        while (left <= i - k)
        {
            left++;
        }

        ans[(*returnSize)++] = nums[q[left]];
    }

    return ans;
}