代码随想录算法训练营第十二天

LeetCode 239. 滑动窗口最大值
- 题目描述
- 思路
- 参考代码
- 总结
LeetCode 347.前 K 个高频元素
- 题目描述
- 思路
- 参考代码

LeetCode 239. 滑动窗口最大值

题目链接：239. 滑动窗口最大值
文章讲解：代码随想录#239. 滑动窗口最大值
视频讲解：单调队列正式登场！| LeetCode：239. 滑动窗口最大值

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例1

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例2

输入：nums = [1], k = 1
输出：[1]

提示

1 <= nums.length <= 10^5
10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

思路

这道题主要是考查队列结构。
对于初次接触的同学，可以先看一下卡哥的讲解视频，然后再结合代码随想录的思路好好推导一下。

以下是我结合卡哥的视频和随想录的思路整理出我对这道题的理解。
说到滑动窗口，想到了之前做的 209.长度最小的子数组，第一反应就是双指针，先对整个数组进行遍历，然后再挨个遍历滑动窗口中的k个数，求出最大值，这样肯定可以解决这道题，不过时间复杂度挺大的，为O(n*k)。
那么有没有时间复杂度较小的解决方案吗？肯定有，那就需要在遍历整个数组时，再配合队列。

队列两端，一边是入口，一边是出口。数组的窗口每次移动时，从队列的出口处pop出要移除的元素，同时需要向队列的入口处push进要添加的元素，然后在队列中找到最大值。
因为要求窗口内的最值，所以我们需要使用到单调队列。
那如何体现是单调队列呢？

每次向队列中push要添加的元素时，需要与队列入口处的元素进行比较。如果要添加的元素大于入口处的元素，则将入口处的元素pop出队列，然后继续比较入口处的下一个元素，直到要添加的元素小于等于入口处的元素或者队列为空，才将该元素push到入口处。（这是关键，保证单调队列是递减的，可以找到最大值）
每次从队列的出口处pop元素时，需要与队列出口处的元素进行比较，如果相等，则将该出口处的元素pop出队列，如果小于，则不需要做任何操作。（在push时，已经将小于的元素pop过了，当前队列中不存在这样的元素，也不存在任何大于的元素，因为在push时添加的就是窗口内最大的元素）

这样队列的出口处就保存了当前窗口中元素的最大值。
因为我们只遍历了一遍数组，所以时间复杂度为O(n)。

参考代码

// 仅供参考，代码没有完全通过
struct quenen {
    int val;
    struct quenen *next;
} Stack;

typedef struct quenen Quenen;

Quenen *quenenCreate() {
    Quenen *obj = (Quenen *)malloc(sizeof(Quenen));
    obj->next = NULL;
    return obj;
}

bool isQuenenEmpty(Quenen *obj)
{
    if (obj->next == NULL) {
        return true;
    }
    return false;
}

int getQuenenTail(Quenen *obj)
{
    Quenen *cur = obj;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    return cur->val;
}

void QuenenPopTail(Quenen *obj)
{
    Quenen *cur = obj;
    while (cur->next != NULL && cur->next->next != NULL) {
        cur = cur->next;
    }

    Quenen *tmp = cur->next;
    cur->next = tmp->next;
    free(tmp);
}

void push(Quenen *obj, int val)
{
    Quenen *cur = obj;
    while (cur->next != NULL) {
        cur = cur->next;
    }

    Quenen *node = (Quenen *)malloc(sizeof(Quenen));
    node->next = NULL;
    node->val = val;
    cur->next = node;
}

int getQuenenHead(Quenen *obj)
{
    return obj->next->val;
}

void QuenenPopHead(Quenen *obj)
{
    Quenen *tmp = obj->next;
    obj->next = tmp->next;
    free(tmp);
}

void quenenPush(Quenen* obj, int x)
{
    while (!isQuenenEmpty(obj) && x > getQuenenTail(obj)) {
        QuenenPopTail(obj);
    }
    push(obj, x);
}

void quenenPop(Quenen* obj, int x)
{
    if (!isQuenenEmpty(obj) && x == getQuenenHead(obj)) {
        QuenenPopHead(obj);
    }
}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
{
    int *ret = (int*)malloc(100000*sizeof(int));
    int cnt = 0;
    Quenen *obj = quenenCreate();

    for (int i = 0; i < k; i++) {
        quenenPush(obj, nums[i]);
    }
    ret[cnt++] = getQuenenHead(obj);

    for (int i = k; i < numsSize; i++) {
        quenenPop(obj, nums[i - k]);
        quenenPush(obj, nums[i]);
        ret[cnt++] = getQuenenHead(obj);
    }
    *returnSize = cnt;

    return ret;
}

总结

看这道题的思路，头一次见到了这些词：单调队列、大顶堆、小顶堆。而这道题用的就是单调队列，所谓的单调队列即队列中的元素是单调递增或单调递减的。
比如，对于单调递减队列来说，队列中存在的元素都是递减，一旦向队列中push了一个比所有元素都要大的值，那需要从队列的入口处依次pop出较小的元素。
我这种写法竟然超时了，数据量一大，单链表操作效率就变得很低了。
改成双链表实现队列，用例总算是通过了，但是效率不高。

参考代码如下

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct quenen {
    int val;
    struct quenen *next;
    struct quenen *pre;
} Stack;

typedef struct quenen Quenen;

Quenen *quenenCreate() {
    Quenen *obj = (Quenen *)malloc(sizeof(Quenen));
    obj->next = obj;
    obj->pre = obj;
    return obj;
}

bool isQuenenEmpty(Quenen *obj)
{
    if (obj->next == obj) {
        return true;
    }
    return false;
}

int getQuenenTail(Quenen *obj)
{
    return obj->pre->val;
}

void QuenenPopTail(Quenen *obj)
{
    Quenen *tmp = obj->pre;
    tmp->pre->next = obj;
    obj->pre = tmp->pre;
    free(tmp);
}

void push(Quenen *obj, int val)
{
    Quenen *node = (Quenen *)malloc(sizeof(Quenen));
    node->val = val;

    node->next = obj;
    node->pre = obj->pre;
    obj->pre->next = node;
    obj->pre = node;
}

int getQuenenHead(Quenen *obj)
{
    return obj->next->val;
}

void QuenenPopHead(Quenen *obj)
{
    Quenen *tmp = obj->next;
    obj->next = tmp->next;
    tmp->next->pre = obj;
    free(tmp);
}