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行的第一个数字。
5423614解释
55入队
544小于队尾5,入队
5422小于队尾4,入队
43新元素3大于队列第二个值2
6新元素大于第一个值6
611小于队尾6
644大于1

纯数组队列代码

/**
 * 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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注