C刷题：LeetCode 239. 滑动窗口最大值（困难）

该题可以优化的点比较多，解决的思路也不少，故特此整理4种解法，并辅以个人在实现时的一些的经验总结，十分有助于开阔解题思路和加深认识。大部分疑难点已在注释里澄清，若有问题，欢迎评论区讨论交流。

基础知识

高级数据结构：大顶堆
两种实现：数组、二叉树
大顶堆：数组到完全二叉树的映射关系是层序遍历，具体见参考资料3里的内容

实现0

自己的思路：用缓存当前窗口三个最值的方法，来降低移出窗的、进入窗的值对最值的影响。

问题在于：不能保证前三个最值，全部匹配当前窗口的前三个最值。当前三个最值挨着的时候，往后挪动三个，最值丢失，只能比较的是新进来的三个当最值，而不能把前面部分的数值再重新考虑进来。

 // 此套逻辑废弃，有漏洞，不能覆盖所有情况
 // 因为不能保证，最大值连续移除时，最大值、次大值、第三大值能实时表示
 // 特别是从第三大值依次往上变为最大值时，不是真正的最大值

 /* 失败用例 [7157,9172,7262,-9146,3087,5117,4046,7726,-1071,6011,5444,-48,-1385,-7328,3255,1600,586,-5160,-371,-5978,9837,3255,-6137,8587,-3403,9775,260,6016,9797,3371,2395,6851,2349,-7019,9318,1211,-3110,8735,-7507,1784,7400,-5799,3169,-7696,-8991,-2222,-9434,-4490,4034,-831,-9656,5488,-4395,9339,4104,-9058,-4072,-1172,1758,6878,-5570,-6380,9550,-9389,1411,2298,3516,551,9196,5215,-237,-4146,1682,4418,-4639,7759,9593,-9588,3041,9208,-7331,-797,-2529,7738,-2944,4351,5091,-9448,-5404,6200,-1425,-3983,678,8456,-8085,5162,7165,4692,-494,-9249,8514,521,-8835,6745,-5775,-575,1876,-5464,5053,5567,3456,5873,1965,4316,2126,9462,-59,6544,-1547,7015,-8928,-3903,-3020,5865,-9479,6723,9214,5705,5136,7725,945,-1995,-2288,4579,7103,9938,4495,-730,-3180,7717,6824,794,-894,-1439,-1641,-4577,9362,-8817,-6035,-7980,-1278,-1928,-5390,-2342,1189,-2340,4788,-1814,5927,3115,9017,6801,7884,-5719,5992,7477,-486,-2734,-1557,3169,5288,-8295,-5651,2491,-3394,8302,-8822,5638,7654,7350,9884,-5392,881,-4874,5582,8309,-8514,2682... 45 */

typedef struct SlidMaxNumInfo {
   
    int max;    // 第1大
    int secMax; // 第2大
    int thrMax; // 第3大
} SlidMaxNumInfoStru, *pSlidMaxNumInfoStru;

void UpdateInMaxValInfo(pSlidMaxNumInfoStru slidMaxInfo, int val)
{
   
    if (val >= slidMaxInfo->max) {
    // 取=是为了避免多个最大值
        slidMaxInfo->thrMax = slidMaxInfo->secMax;
        slidMaxInfo->secMax = slidMaxInfo->max;
        slidMaxInfo->max = val;
    } else if (val >= slidMaxInfo->secMax) {
   
        slidMaxInfo->thrMax = slidMaxInfo->secMax;
        slidMaxInfo->secMax = val;
    } else if (val >= slidMaxInfo->thrMax) {
   
        slidMaxInfo->thrMax = val;
    }
    return;
}

void UpdateOutMaxValInfo(pSlidMaxNumInfoStru slidMaxInfo, int val, int* maxOutCnt)
{
   
    if (val == slidMaxInfo->max) {
   
        slidMaxInfo->max = slidMaxInfo->secMax;
        slidMaxInfo->secMax = slidMaxInfo->thrMax;
        slidMaxInfo->thrMax= INT_MIN;
        (*maxOutCnt)++;
    } else if (val == slidMaxInfo->secMax) {
   
        slidMaxInfo->secMax = slidMaxInfo->thrMax;
        slidMaxInfo->thrMax= INT_MIN;
    } else if (val == slidMaxInfo->thrMax) {
   
        slidMaxInfo->thrMax= INT_MIN;
    }
    return;
}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
{
   
    // 已保证输入 k < numSize
    // k = 1 直接输出数组

    if (k == 1) {
   
        *returnSize = numsSize;
        return nums;
    }

    // k != 1
    int resSize = numsSize - k + 1;
    *returnSize = resSize;
    SlidMaxNumInfoStru slidMaxInfo = {
   INT_MIN, INT_MIN, INT_MIN};
    int *resArr = (int *)malloc(*returnSize * sizeof(int));
    if (resArr == NULL) {
    return NULL; }
    int cnt = 0;
    
    int start = 0;
    int end = 0;
    int *p = resArr;

    // 初始化第一个窗口
    end = start;
    while (end < start + k) {
   
        UpdateInMaxValInfo(&slidMaxInfo, nums[end]);
        end++;
    }

    // 开始往后滑动
    *p = slidMaxInfo.max;
    p++;
    start++;
    while (start < resSize) {
   
        // 先匹配可行解，滑动到右侧，并找到最大值
    
        // 缩小范围，找到次大值

        // 更新当前窗口最大值，滑动窗口
        UpdateOutMaxValInfo(&slidMaxInfo, nums[start - 1], &cnt);
        if (cnt == 2) {
   
            end = start;
            while (end < start + k) {
   
                UpdateInMaxValInfo(&slidMaxInfo, nums[end]);
                end++;
            }
            cnt = 0;
            end--;
        } else {
   
            UpdateInMaxValInfo(&slidMaxInfo, nums[end]);
        }
        
        *p = slidMaxInfo.max;
        p++;

        // 滑动
        start++;
        end++;
    }

    return resArr;
}

实现1

参考LeetCode官方题解思路，自己独立实现后可以通过，但是由于完全用选择排序数组来实现的最大堆，面对大数据时，会超出时间限制。

优化点：将push和pop从O(N)优化到 O(logN)，不要相邻的交换复制。采用完全二叉树的表示，但依然用数组的结构，由于顶端都是最大值，就可以用二分法来调整堆的结构。

/** * Note: The returned array must be malloced, assume caller calls free(). */

// Prior Quneue，完全用数组形式实现的最大堆功能
typedef struct MaxPriorQue {
   
    int** heap;  // 二维数组 heap[i][0/1] 0是idx,1是val
    int size;    // 当前队列大小
    int capcity; // 队列最大容量
} MaxPriorQueStru, *pMaxPriorQueStru;

void init(pMaxPriorQueStru p, int size)
{
   
    p->size = 0;
    p->heap = (int**)malloc(size * sizeof(int*));
    // if (p->heap == NULL) { return NULL;}
    p->capcity = size;

    int i;
    for (i = 0; i < p->capcity; i++) {
   
        p->heap[i] = (int *)malloc(2 * sizeof(int));
        // if (p->heap[i] == NULL) { return NULL; }
    }

    return;
}

// 完全用数组形式实现的最大堆功能
void push(pMaxPriorQueStru p, int idx, int val)
{
   
    // 已保证堆足够大，不用担心溢出
    int top = p->size++;

    // 调整堆
    // 先复制交换二级指针存储的地址，找到插入位后再赋值
    int i = top - 1;
    //int *tmp = p->heap[top];
    while ((i >= 0) && (p->heap[i][1] > val)) {
   
        p->heap[i + 1][0] = p->heap[i][0];
        p->heap[i + 1][1] = p->heap[i][1];
        i--;
    }
    if (i < 0) {
   
        // p->heap[0] = tmp;
        p->heap[0][0] = idx;
        p->heap[0][1] = val;
    } else {
   
        // p->heap[i + 1] = tmp;
        p->heap[i + 1][0] = idx;
        p->heap[i + 1][1] = val;
    }

    return;
}

void pop(pMaxPriorQueStru p)
{
   
    p->size = p->size - 1;
    return;
}

int* top(pMaxPriorQueStru p)
{
   
    return p->heap[p->size - 1];
}

void SetFree(pMaxPriorQueStru p)
{
   
    int i;
    for (i = 0; i < p->capcity; i++) {
   
        free(p->heap[i]);
    }
    free(p->heap);
    free(p);
    return;
}

// 利用最大堆队列数据结构来完成
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
{
   
    if (k == 1) {
   
        *returnSize = numsSize;
        return nums;
    }

    // 压入前k个数据
    pMaxPriorQueStru q = (pMaxPriorQueStru)malloc(sizeof(MaxPriorQueStru));
    if (q == NULL) {
    return NULL; }
    init(q, numsSize);

    int resSize = numsSize - k + 1;
    int *resArr = (int *)malloc(resSize * sizeof(int));
    if (resArr == NULL) {
    return NULL; }

    int end = 0;
    int i;
    for (i = 0; i < k; i++) {
   
        push(q, i, nums[i]);
    }
    int *heap = top(q);
    // resArr[*returnSize++] = heap[1]; // 作用是：resArr[*returnSize], 再returnSize++，加在地址上了，与预期不符
    resArr[end++] = heap[1];
    //printf("%d \n", *returnSize);
    //printf("%d ", heap[1]);

    // 从k往后移动
    for (i = k; i < numsSize; i++) {
   
        push(q, i, nums[i]);
        heap = top(q);
        while (heap[0] <= i - k) {
   
            pop(q);
            heap = top(q);
        }
        //resArr[*returnSize++] = heap[1];
        resArr[end++] = heap[1];
        // printf("%d \n", *returnSize);
        // printf("%d ", heap[1]);
    }
    //printf("%d \n", *returnSize);

    *returnSize = end;
    SetFree(q);

    return resArr;
}

实现2

改进实现1中的pop()和push()等相关函数。首先分析理解官方题解用意，详细注释如下：

void swap(int** a, int** b) {
   
    int* tmp = *a;
    *a = *b, *b = tmp;
}

int cmp(int* a, int* b) {
   
	 // 优先比较数值，其次再比较索引，索引大的在窗右侧更新，放上一层
    return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
}

void push(struct Heap* obj, int num0, int num1) {
   
    int sub1 = ++(obj->size), sub2 = sub1 >> 1; 
    (obj->heap[sub1])[0] = num0, (obj->heap[sub1])[1] = num1; // 把新插入的值放到堆的末尾
    // 找二叉树上一层最右侧的叶子节点比较
    while (sub2 > 0 && cmp(obj->heap[sub2], obj->heap[sub1]) < 0) {
    
     	// 若上一层sub2叶子节点 < 新插入的sub1叶子节点，则交换位置
        swap(&(obj->heap[sub1]), &(obj->heap[sub2]));
        sub1 = sub2, sub2 = sub1 >> 1; // 继续往上一层比较
    }
    // 到达顶端或者新插入的值比上一层叶子节点小已找到对应位置
}

void pop(struct Heap* obj) {
   
    int sub = 1;
    // 待删除的顶端位置与末端节点交换，然后减小
    swap(&(obj->heap[sub]), &(obj->heap[(obj->size)--])); 
    while (sub <= obj->size) {
    // 从上往下调整最大堆
    	 // sub1为左孩子索引，sub2=sub1+1为右孩子索引
        int sub1 = sub << 1, sub2 = sub << 1 | 1;
        int maxSub = sub; // 假设当前父节点是最大值
        if (sub1 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub1]) < 0) {
    // 左孩子比maxSub节点大，交换
            maxSub = sub1;
        }
        if (sub2 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub2]) < 0) {
    // 右孩子比maxSub节点大，交换
            maxSub = sub2;
        }
        if (sub == maxSub) {
    // 无交换，父节点已最大，则堆已调整完毕，不需要再往下调整
            break;
        }
        swap(&(obj->heap[sub]), &(obj->heap[maxSub])); // 如果有交换，则交换指针位置
        sub = maxSub; // 交换后，下沉到交换后的索引位置
    }
    // break跳出或者已调整到末端节点退出
}

将以下修改点对应的代码替代实现1中对应部分，即可提交通过：

增加比较函数cmpValOrIdx()
修改init()
修改pop()
修改push()
修改top()

注意点：
为方便运算，0索引位置空出来不存储，上一层的末尾叶节点下标索引为当前插入值下标索引除以2。

int cmpValOrIdx(int *a, int *b)
{
   
    return a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]; // 优先比较数值，再比较下标
}

void init(pMaxPriorQueStru p, int size)
{
   
    p->size = 0;
    p->heap = (int**)malloc((size + 1) * sizeof(int*));
    // if (p->heap == NULL) { return NULL;}
    p->capcity = size + 1;

    int i;
    for (i = 0; i < p->capcity; i++) {
   
        p->heap[i] = (int *)malloc(2 * sizeof(int));
        // if (p->heap[i] == NULL) { return NULL; }
    }

    return;
}

// 完全用数组形式实现的最大堆功能
void push(pMaxPriorQueStru p, int idx, int val)
{
   
    // 已保证堆足够大，不用担心溢出
    p->size += 1;

    // 先放末端节点
    p->heap[p->size][0] = idx;
    p->heap[p->size][1] = val;

    // 通过与上层节点不断比较交换，找到合适位置
    int i0 = p->size >> 1;
    int i1 = p->size;
    while (i0 > 0 && cmpValOrIdx(p->heap[i0], p->heap[i1]) < 0) {
   
        int *tmp = p->heap[i0]; // 交换二级指针指向的一级指针地址
        p->heap[i0] = p->heap[i1];
        p->heap[i1] = tmp;
        i1 = i0; // 继续往上一层末端节点比较
        i0 >>= 1;
    }

    return;
}

void pop(pMaxPriorQueStru p)
{
   
    // 将顶端的值与末尾节点交换，再自减容量
    int *tmp = p->heap[1]; // 交换二级指针指向的一级指针地址
    p->heap[1] = p->heap[p->size];
    p->heap[p->size] = tmp;
    p->size--;

    // 调整堆，把末尾节点下沉到合适位置
    int i = 1; // 从顶端开始
    while (i <= p->size) {
   
        int l = i << 1; // 左孩子索引
        int r = l + 1; // 右孩子索引
        int max = i;
        if (l <= p->size && cmpValOrIdx(p->heap[max], p->heap[l]) < 0) {
   
            max = l;
        }
        if (r <= p->size && cmpValOrIdx(p->heap[max], p->heap[r]) < 0) {
   
            max = r;
        }
        if (max == i) {
    // 如果父节点就已是最大值，则调整完毕，顶端交换的值已找到合适位置
            break;
        }
        // 需要交换
        int *tmp = p->heap[i]; // 交换二级指针指向的一级指针地址
        p->heap[i] = p->heap[max];
        p->heap[max] = tmp;

        i = max; // 和max的指针交换后，当前max索引是被交换到顶端的底部值，待进一步下沉比较
    }
    // i下沉到最末端或者末尾节点已下沉到合适位置，结束调整

    return;
}

int* top(pMaxPriorQueStru p)
{
   
    return p->heap[1]; // 为方便下标引用，索引0空置不用
}

实现3

参考LeetCode官方题解方法二思路，继续优化，将实现0的思路改进成单调队列，不仅只存3个最值，而是动态存储更新当前窗的最值，依次单调递减。

思路核心点：

申请一个与输入数组同样大小的数组maxQueIdx，作为单调队列
队列存储的只是输入数组对应元素的索引
单调队列的数组maxQueIdx下标范围[left, right)
队首left始终是当前窗口最大值的索引，right指向队尾元素的下一个位置，队列从左到右单调递减
队列更新：
- 比较移入窗口的元素，若比队尾元素小，则直接入队尾；否则，队尾元素出队right--，直到比队尾元素小，再入队；（更新最值）
- 判断当前队首元素索引是否在当前窗内，不在的话需要队首出队left++（说明当前队列最大值刚被移出窗了）

独立实现代码如下：

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
{
   
    if (k == 1) {
   
        *returnSize = numsSize;
        return nums;
    }
    // 单调队列思路，从左到右递减；思路类同第一个保存第一第二个最大值思路
    int maxQueIdx[numsSize];
    int resSize = numsSize - k + 1;
    int *resArr = (int *)malloc(resSize * sizeof(int));
    if (resArr == NULL) {
    return NULL; }
    *returnSize = resSize;

    int i;
    int left = 0;
    int right = 0;
    for (i = 0; i < k; i++) {
   
        while (left < right && nums[i] >= nums[maxQueIdx[right - 1]]) {
   
            right--; // 出队列
        }
        maxQueIdx[right++] = i;
    }
    resSize = 0;
    resArr[resSize++] =  nums[maxQueIdx[left]];

    for (i = k; i < numsSize; i++) {
   
        // 若窗口加入的新元素比队尾元素大于等于，则队尾元素出队列 
        // 之所以等于也要出队列，是因为下标idx最新，不容易移除窗口
        while (left < right && nums[i] >= nums[maxQueIdx[right - 1]]) {
    // 当前队尾元素为right - 1,队尾指针在right
            right--; // 出队列
        }
        maxQueIdx[right++] = i;

        while (maxQueIdx[left] <= i - k) {
    // 最大值不在窗外
            left++; // 弹出队首元素，左移
        }
        resArr[resSize++] =  nums[maxQueIdx[left]];
    }

    return resArr;
}

C刷题：LeetCode 239. 滑动窗口最大值 （困难）