滑动窗口的最大值

#include <string.h>
#include <stdbool.h>
#include <stdio.h>
int *queue, queueSize, *topQueue=NULL, *bottomQueue=NULL;

void createQueue(int size) {
    queue = (int*)malloc(size*sizeof(int));
    memset((unsigned char*)queue, 0, size*sizeof(int));
    queueSize = size;
}

int top() {
    if(topQueue==NULL)
        return 0;
    return *topQueue;
}

int bottom() {
    if(bottomQueue==NULL)
        return 0;
    return *bottomQueue;
}

int len() {
    if(bottomQueue==NULL)
        return 0;
    if(topQueue <= bottomQueue)
        return bottomQueue-topQueue+1;
    else
        return queueSize-(topQueue-bottomQueue)+1;
}

int push(int node ) {   
    if(bottomQueue==NULL) {
        bottomQueue = queue;
        topQueue = queue;
    }
    else {
        if(topQueue-bottomQueue==1 || (topQueue==queue && bottomQueue==(queue+queueSize-1))) 
            return -1;
        
        if(bottomQueue == queue+queueSize-1) 
            bottomQueue = queue;
        else 
            bottomQueue++;
    }
    *bottomQueue = node;
    return 0;
}

int pop(int *node) {
    if(topQueue == NULL)
        return -1;
        
    if(node!=NULL)
        *node = *topQueue;
    *topQueue = 0;
    if(bottomQueue == topQueue) {
        bottomQueue = NULL;
        topQueue = NULL;
    }
    else {
        if(topQueue == queue+queueSize-1)
            topQueue = queue;
        else 
            topQueue++;
    }     
    return 0;
}

int max() {
    int res=top();
    int *q=topQueue;
    if(q!=NULL)
        while(q!=bottomQueue) {
            if(res<*q)
                res = *q;
            if(q == queue+queueSize-1)
                q = queue;
            else 
                q++;
        }
        if(res<*q)
            res = *q;
    return res;
}

int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    int *res,i;
    if(size>numLen) {
        *returnSize = 0;
        return NULL;
    }
    if(size==0)
        return num;
    res = (int*)malloc((numLen-size+1)*sizeof(int));
    createQueue(size);
    for(i=0; i<numLen; i++) {
        if(push(num[i])){
            pop(NULL);
            push(num[i]);
        }
        if(i>=size-1) 
            res[i-size+1] = max();
    }
    *returnSize = numLen-size+1;
    return res;
}

这题不需要用太多数据结构的知识。不知道为什么这个题目会进入困难。普通数组的处理就行

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @param size int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* maxInWindows(int* num, int numLen, int size, int* returnSize ) 
{
    //num指向传入函数的数组，numLen为传入数组的长度。size为滑动窗口的大小
    // write code here
    //特殊情况校验
    if(size > numLen || size == 0)
    {
        return NULL;
    }

    // printf("%d",size);
    static int maxnum[10000];
    int max = -10000;  //暂时保存最大值
    //设定滑动窗口的起始和末尾初始定标
    int start = 0; int last = size;
    //在滑动窗口中找最大值。实际就是在后续每次比较把多进来的一个数值进行比较即可
    //进行第一轮定标。要把size大小内的元素都过一遍
    int flownum = numLen - size + 1;  //滑动窗口一共的滑动次数
    while(flownum)  //到0为最终结果
    {
        for(int i = start; i < last; i++)
        {
            if(num[i] > max)
            {
                max = num[i];
            }
        }
        maxnum[start] = max;  //找到滑动窗口的最大值
        (*returnSize)++;
        start++; last++;
        flownum--;
        max = -10000;  //每个滑动窗口内都会有不同的最大值。所以把max每次置为最小值就可以找到那个大值
    }

    return maxnum;
}

int* maxInWindows(int* num, int numLen, int size, int* returnSize ) 
{
    if(size > numLen || size == 0)
    {
        return NULL;
    }
    int left = 0,right = size - 1; //确定窗口区间
    int max = num[0];
    *returnSize = numLen - size + 1;//确定返回数组数据个数

    int *res = (int *)malloc(sizeof(int) * (*returnSize));
    int k = 0;

    while(right < numLen)
    {
        for(int i = left;i <= right;i++)
        {
            if(max < num[i])
            {
                max = num[i];
            }
        }

        res[k++] = max;
        left++,right++;//改变窗区间并修改max值
        max = num[left];
    }

    return res;
}

int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    // write code here
    if(size > numLen || size == 0)//窗口大于数组长度或窗口长度为0的时候，返回空。
        return NULL;
    int index = -1;//记录最大值的下标,防止出现更新的窗口最右边的数一直不大于原有的max
    int left = 0,right = size-1;
    int max = num[0];//保存最大值
    *returnSize = numLen - size + 1;//窗口的大小
    int *res = (int *)malloc(sizeof(int) * (*returnSize));
    int k = 0;

    while(right<numLen)
    {
        if(index<left)//下标小于left时没更新max，需更新max，index设置为-1也可进行循环
        {
            max = num[left];
            for(int i = left;i<=right;i++)
            {
                if(max < num[i])
                {
                    index = i;
                    max = num[i];
                }
            }
        }

        if(max<num[right])//此情况为窗口滑动一下就有比当前max更大的值进入窗口，更新max
        {
            max = num[right];
            index = right;
        }

        res[k++] = max;
        left++,right++;
    }
    return res;
}

/**
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @param size int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

typedef struct alog
{
     int(*find_max_val)(int* ,int );
     void(*traverse_array)(struct alog,int*,int ,int,int* );
}alog_max;
static  int find_max_val(int* subarray,int win_size)
{
    int cnt = 0;
    int max_val = -1;
    for(;cnt<win_size;cnt++){
         if(max_val<subarray[cnt]){
             max_val = subarray[cnt];
         }
    }
    return max_val;
}
static  void traverse_array( struct alog my_alog,int* num,int numLen,int win_size,int* rst)
{
    int cnt = 0;
    for(;cnt<numLen-win_size+1;cnt++){
        rst[cnt] = my_alog.find_max_val(&num[cnt],win_size);
    }
}
static struct alog my_alog = {
    .find_max_val = find_max_val,
    .traverse_array = traverse_array,
};
int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    // write code here
    if(numLen<size||size<0||num==NULL){
        return NULL;
    }
    int* rst = malloc(numLen*sizeof(int));
    my_alog.traverse_array(my_alog,num,numLen,size,rst);
    *returnSize = numLen-size+1;
    return rst;
}

//队列思想解决
typedef struct elem{
    int num;
    int index;
}elem;
int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    // write code here
    if(numLen<size || size ==0){
        return NULL;
    }
    if(size==1){
        *returnSize=numLen;
        return num;
    }

    *returnSize=0;
    int i,beg=0,end=0,*max;
    max = (int*)malloc(4*(numLen-size+1));
    elem arr[numLen+1];
    
    arr[0].num=num[0];  //当为空时
    arr[0].index=0;
    end++;

    for(i=1;i<size;i++){//第一个窗口
            if(arr[end-1].num>num[i]){
                arr[end].num=num[i];
                arr[end].index=i;
                end++;
            }else{
                int j;
                end--;
                for(j=end-1;j>=beg;j--){
                    if(arr[j].num<num[i]){
                        end--;
                    }
                }
                arr[end].num=num[i];
                arr[end].index= i;
                end++;
            }
    }
    (*returnSize)++;
    max[0]=arr[beg].num;

    for(i=size;i<numLen;i++){//其余窗口
        if(arr[beg].index<=i-size){
            beg++;
        }
        if(arr[end-1].num>num[i]){
                arr[end].num=num[i];
                arr[end].index=i;
                end++;
            }else{
                int j;
                end--;
                for(j=end-1;j>=beg;j--){
                    if(arr[j].num<num[i]){
                        end--;
                    }
                }
                arr[end].num=num[i];
                arr[end].index= i;
                end++;
            }
        max[(*returnSize)]=arr[beg].num;
        (*returnSize)++;
    }
    return max;
}