题解 | #滑动窗口的最大值#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @param size int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
#include <malloc.h>
#include <stdlib.h>
int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    // write code here
    if(numLen < size || size == 0 ) //首先考虑边界条件
    {
        int *ans = (int *)malloc(0);
        return ans;
    }

    int count = numLen - size + 1;  //滑动窗口个数
    int *ans = (int *)malloc(sizeof(int) * count);
    int cnt = 0;
    int left = 0, right = 0;    //双指针滑动窗口，左闭右开
    int max = num[left];
    while(right <= numLen)  //左闭右开区间，right最终指向数组后一位，因此可以等于nunLen，但是不能超过
    {
        int a = num[right]; //弹出当前元素 扩大窗口
        if(a >= max)    //这里一定要>=而不能是>，否则如果第一次循环刚好第一个是0又恰好是最大值，那么将无法记录第一个元素
        {
            max = a;
        }
        right++;    //弹出元素后可以扩大窗口

        while(right - left >= size) //区间长度等于滑窗大小时开始收缩窗口,同时为了保证最后一个窗口的值能正确记录，需要后一个条件来保证最后一次记录
        {
            ans[cnt] = max; //存储最大值
            cnt++;  //计数加1

            int b = num[left];  //弹出窗口左边元素
            left++; //收缩窗口
            if(b == max)    //如果弹出的是最大值，那么要移动左指针重新寻找最大值,直到当前right指针前一个位置
            {
                max = num[left];    //重置最大值
                int virtule_left = left + 1;    
                while(virtule_left < right) //寻找当前窗口的最大值，但是不能缩小窗口，否则会导致滑窗数量不够
                {
                    if(num[virtule_left] >= max)
                    {
                        max = num[virtule_left];
                    }
                    virtule_left++; //不管有没有更新max，指针都要加1，否则进入死循环，属于逻辑错误
                }
            }
        }
    }

    *returnSize = count;
    return ans;

}

本题比较难，很容易在细节处出现bug。题目已经很明显的暗示使用双指针中的滑动窗口算法，关键在于更新max的操作有很多细节需要处理，以及收缩窗口时并不能像普通滑动窗口算法一样把窗口收缩到0，这道题只能收缩到size-1，否则会导致滑窗数量不够，这是本题我认为最大的坑。