LeetCode-简单-剑指 Offer 59-滑动窗口的最大值-队列解法(C)

在找数据结构的题的时候,队列第一题就是这个。
虽然不用队列会更好做,效率也高,但还是用队列来了。

这题在大题库里面是239题,困难难度,但我找到的是剑指 Offer第59题,简单难度。
题目是一样的,但是测试案例,困难的有60个测试,简单只有18个。
但是这个代码在239题不通过,会在第49个测试的50000长度的滑动窗口里面超时。

题目

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例:

输入: 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
 

提示:

你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

注意:本题与主站 239 题相同:https://leetcode-cn.com/problems/sliding-window-maximum/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  • 用的队列解法,对于这题会产生不少消耗:
    • 建立一个长度为k的队列,从nums[]的头移动到尾,每次都判断一下最大值。

代码

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

typedef struct qNode{
    int val;
    struct qNode* next;
}qNode;

typedef struct queue{
    qNode* front;
    qNode* rear;
}queue;

queue* createQueue();
void addQueue(queue* q, int val);
void removeQueue(queue* q);
void printQueue(queue* q);
int maxValueInQueue(queue* q);

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    if(numsSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    *returnSize = numsSize - k + 1;
    queue* q = createQueue();
    int* returnArray = malloc(sizeof(int) * *returnSize);
    int pos;
    for(pos = 0;    pos<k;    pos++){
        addQueue(q, nums[pos]);
    }
    returnArray[0] = maxValueInQueue(q);
    for(pos = k;    pos<numsSize;    pos++){
        addQueue(q, nums[pos]);
        removeQueue(q);
        returnArray[pos - k + 1] = maxValueInQueue(q);
    }
    return returnArray;

}

int maxValueInQueue(queue* q){
    qNode *node = q->front;
    int max = node->val;
    while(node){
        max = max > node->val ? max : node->val;
        node = node->next;
    }
    return max;
}

queue* createQueue(){
    queue* q = malloc(sizeof(queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void addQueue(queue* q, int val){
    qNode* node = malloc(sizeof(qNode));
    node->val = val;
    node->next = NULL;
    if(q->front){
        q->rear->next = node;
        q->rear = node;
    }
    else{
        q->front = q->rear = node;
    }
}

void removeQueue(queue* q){
    qNode* temp;
    temp = q->front;
    if(q->front != q->rear){
        q->front = q->front->next;
    }
    else if(!q->front){
        puts("error remove.");
    }
    else{
        q->front = NULL;
        q->rear = NULL;
    }
    free(temp);
}

void printQueue(queue* q){
    qNode* node = q->front;
    while(q->front){
        printf("%d ", node->val);
        node = node->next;
    }
    puts("");
}

You may also like...

发表评论

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