LeetCode-困难-239-滑动窗口的最大值-队列/二分法(C)

LeetCode题解目录

之前的同样的一道题：LeetCode-简单-剑指 Offer 59-滑动窗口的最大值-队列解法(C)
在这里的解法会超时，所以今天换了新算法，刚开始试的是两个值表示窗口的无脑算法。
然后发现原来这题对我来说真的得用队列才能解，只是之前的队列效率不高而已...
之前用的是变长链表队列，这次的是定长数组队列。

题目

给你一个整数数组 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]
示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：

输入：nums = [9,11], k = 2
输出：[11]
示例 5：

输入：nums = [4,-2], k = 2
输出：[4]
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 参考：双向队列解决滑动窗口最大值
• 这题差点就被我放弃了，好多个解法都超时，然后去看了题解，了不得了不得啊。
• 用队列来解决：
  • 选用了定长的数组队列：
    • 为了浪费更大的空间（但leetcode内存消耗反而更低）。
    • 方便实现队尾前进后退。
  • 队列中保存的是nums[]的下标：
    • 方便判断队头是否还在滑动窗口内。
  • 队列中元素必是从大到小排列：
    • 如果待入队的值 >= 队头，那么其将在未来很长一段时间内作为滑动窗口的最大值。
      • 直到出现比他更大的，或者该值离开了滑动窗口。
      • 实际上这个操作和下面的操作是一致的，但加上它可以减少部分计算量。
        • 比如队列中有5w个元素，新元素比第一个值大。
    • 如果出现了一个值，大小处于队列中间，那么将队列中小于它的值全部退出，再让其入队。
• 如果想要提高效率，可以在上行中的队尾移动操作的地方做修改，用二分法来搜索，而不是遍历。
  • 但因为这里的队列尾巴与头的位置不一定，可能头在前，也可能尾在前，所以二分法的修改有点麻烦，我今天不太想废头发了。
    • 然后睡觉前想了一下，发现好像只要在第一次用边界区分一下就好了，于是第二天又改进了算法。
    • 但效率并没有提高。
    • 淦。
• 下面举一个例子，滑动窗口大小为3：
  • 其中，窗口的右端从0开始滑动，即前两次滑动没有结果
  • 下面除第一行与最后一列外的位置，如果有数字，表示该值在队列，如果是 - ，表示该值在窗口内，但不在队列中。
  • 滑动窗口的最大值为第4行至第7行的第一个数字。

纯数组队列代码

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

typedef struct queue{
    int* node;
    int front;
    int rear;
    int maxLength;
}queue;

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    int i;
    queue* q;
    *returnSize = numsSize - k + 1;
    int* returnArray = malloc(sizeof(int) * *returnSize);

    //队列初始化
    q = malloc(sizeof(queue));
    q->node = malloc(sizeof(int) * k);
    q->front = q->rear = q->node[0] = 0;
    q->maxLength = k;
    for(i=1;    i<k-1;    i++){
        enqueue(q, i, nums);
    }

    //通过定制的入队函数获得每个滑动窗口的最大值
    for(i=k-1;   i<numsSize; i++){
        returnArray[i - k + 1] = enqueue(q, i, nums);
    }
    return returnArray;
}

int enqueue(queue* q, int pos, int* nums){
    if(nums[pos] >= nums[q->node[q->front]]){   
        //新加入的比队头大，直接清空队列并将队头设置为新位置
        q->rear = q->front;
        q->node[q->front] = pos;
        return nums[pos];
    }
    else if(pos - q->maxLength + 1 > q->node[q->front]){    
        //队头不在滑动窗口内，队头退出
        q->front = (q->front + 1) % q->maxLength;
    }
    while(q->node[q->rear] >= q->node[q->front] && nums[q->node[q->rear]] <= nums[pos]){
        //回退队尾，回退至第一个大于pos值的位置。
        q->rear = (q->rear - 1 + q->maxLength) % q->maxLength;       
    }
    q->rear = (q->rear + 1) % q->maxLength; //队尾后移
    q->node[q->rear] = pos; //pos入队
    return nums[q->node[q->front]];
}

二分搜索改进后的代码

• 效率没有显著提升，还浪费了我不少头发，可恶。
• 与上段代码仅回退队尾的地方不同，改成了二分搜索来回退队尾，而不是直接回退。

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

typedef struct queue{
    int* node;
    int front;
    int rear;
    int maxLength;
}queue;

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    int i;
    queue* q;
    *returnSize = numsSize - k + 1;
    int* returnArray = malloc(sizeof(int) * *returnSize);

    //队列初始化
    q = malloc(sizeof(queue));
    q->node = malloc(sizeof(int) * k);
    q->front = q->rear = q->node[0] = 0;
    q->maxLength = k;
    for(i=1;    i<k-1;    i++){
        enqueue(q, i, nums);
    }

    //通过定制的入队函数获得每个滑动窗口的最大值
    for(i=k-1;   i<numsSize; i++){
        returnArray[i - k + 1] = enqueue(q, i, nums);
    }
    return returnArray;
}

int enqueue(queue* q, int pos, int* nums){
    if(nums[pos] >= nums[q->node[q->front]]){   
        //新加入的比队头大，直接清空队列并将队头设置为新位置
        q->rear = q->front;
        q->node[q->front] = pos;
        return nums[pos];
    }
    else if(pos - q->maxLength + 1 > q->node[q->front]){    
        //队头不在滑动窗口内，队头退出
        q->front = (q->front + 1) % q->maxLength;
    }

    //回退队尾，回退至第一个大于pos值的位置。
    if(q->front <= q->rear){
        q->rear = binarySearch(q, q->front, q->rear, nums[pos], nums);
    }
    else if(nums[q->node[0]] > nums[pos]){
        q->rear = binarySearch(q, 0, q->rear, nums[pos], nums);
    }
    else{
        q->rear = binarySearch(q, q->front, q->maxLength-1, nums[pos], nums);
    }

    q->rear = (q->rear + 1) % q->maxLength; //队尾后移
    q->node[q->rear] = pos; //pos入队
    return nums[q->node[q->front]];
}

int binarySearch(queue* q, int left, int right, int target, int* nums){
    int temp, mid;
    mid = (left + right) / 2;
    if(nums[q->node[left]] < target){
        return (left - 1 + q->maxLength) % q->maxLength;
    }
    else if(left + 1 == right){
        if(nums[q->node[right]] > target) return right;
        else return left;
    }
    if(nums[q->node[right]] >= target){
        return right;
    }
    else if(nums[q->node[mid]] >= target){
        temp = (mid + 1) % q->maxLength;
        if(nums[q->node[mid]] < target) return mid;
        else return binarySearch(q, mid, right, target, nums);
    }
    else if(nums[q->node[left]] >= target){
        temp = (left + 1) % q->maxLength;
        if(nums[q->node[temp]] < target) return left;
        else return binarySearch(q, left, mid, target, nums);
    }
    return right;
}