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("");
}