滑动窗口最大值问题

滑动窗口最大值问题

leetcode原题链接： . - 力扣（LeetCode）

思路：滑动窗口，在数组位置建立一个双端队列利用出入队列来模拟窗口平移，即首先把第一个窗口入进去，接着i遍历原数组剩下的元素，每次入剩下的元素相当于窗口右移，对于维护窗口即维护队列，由于要的是每次得到的窗口中最大值故当每次入队列的时候，比较原值和队列放的队尾下标对应的值，如果原值大即right--，把它往队前放，反之放后面 目的：（每次队列中放入的是原数组下标，这样操作为了保证队列中的下标是升序，对应的值为降序，每次取窗口的最大值，即left处值）（可能队列中数据不足k个但由于每次只要最大值，即left处，可以控制当每次新入数据，通过维护队列，使得left处为最大值，只要保证每次队列数据<=k即可）。

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    int queue[numsSize];//这里下标是numsSize不是k+1，由于队列即会在原数组内滑动，故下标会变化但队列内元素最大是k+1
    int left=0;
    int right=0;
    int size=numsSize-k+1;//窗口个数，即最大值个数
    *returnSize=0;
    for(int i=0;i<k;i++){//先把第一组窗口数据入队列
        while(left<right&&nums[i]>=nums[queue[right-1]]){
            right--;//按照下标升序，对应值降序排列（可能会<k个）
        }
        queue[right++]=i;
    }
    int*ret=(int*)calloc(size,sizeof(int));
    ret[(*returnSize)++]=nums[queue[left]];//得到第一个窗口的最大值
    for(int i=k;i<numsSize;i++){//i往后遍历数组，即窗口后移
         while(left<right&&nums[i]>=nums[queue[right-1]]){
            right--;
        }
        queue[right++]=i;//先把后面遍历到的i放入，然后情况可能是：1·对应值最大被移到了left剩下的覆盖掉：2·在中间位置；·最小直接插后面
        if(queue[left]+k<=i){//有可能队列内的数据个数为k+1即最大程度，这时由于队列中的下标按照升序排列，即对应的原数组的顺序，即这个窗口要包含此时入的数据，需要left出队列即left++;
            left++;//由于每次入队列的数据都进行判断故最大数据个数为k+1，只需要移动一次所以用if而不是while
        }
        

        ret[(*returnSize)++]=nums[queue[left]];   
    }
    
    return ret;
}