滑动窗口的最大值

C 解法, 执行用时: 24ms, 内存消耗: 2684KB, 提交时间: 2021-12-09

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

int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    // write code here
    if(numLen < size || size <= 0) return NULL;
    int *res = malloc(numLen * sizeof(int));
    int max = -1;
    for(int i = size - 1, maxVal = 0; i < numLen;i++){
        if( max + size == i){
            maxVal = num[i];
            for(int j = i - size + 1;j <= i ;j++){
                if(num[j] >= maxVal){
                    maxVal = num[max = j];
                }
            }
        }else if(maxVal <= num[i]){
            maxVal = num[max = i];
        }
        res[(*returnSize)++] = maxVal;
    }
    return res;
}

C 解法, 执行用时: 25ms, 内存消耗: 2644KB, 提交时间: 2022-04-19

int* maxInWindows(int* nums, int numsSize, int k, int* returnSize ) {
    // write code here
    *returnSize = 0;
    if (numsSize == 0) {
        return NULL;
    }
    int* queue = malloc(sizeof(int) * numsSize);
    int head = 0, tail = 0;
    for (int i = 0; i < k; i++) {
        while (head < tail && nums[i] > nums[queue[tail - 1]]) {
            tail--;
        }
        queue[tail++] = i;
    }
    int* res = (int*)malloc(sizeof(int) * (numsSize - k + 1));
    res[(*returnSize)++] = nums[queue[head]];
    for (int i = k; i < numsSize; i++) {
        while (head < tail && nums[i] > nums[queue[tail - 1]]) {
            tail--;
        }
        queue[tail++] = i;
        while (queue[head] <= i - k) {
            head++;
        }
        res[(*returnSize)++] = nums[queue[head]];
    }
    return res;
}

C 解法, 执行用时: 25ms, 内存消耗: 2648KB, 提交时间: 2022-03-08

/**
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @param size int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int maxwhere(int* num,int start,int size){
    int max=*(num+start),where=start;
    for(int i =1;i<size;i++){
        if(max<*(num+start+i)){
            max=*(num+start+i);
            where=start+i;
        }
    }
     printf("InFunction:%d ",where);
    return where;
}
int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    // write code here
    if(size>numLen||size==0) return NULL;
    *returnSize=numLen-size+1;
    if(size==1) return num;
    int* result = (int*)malloc(sizeof(int)*(numLen-size+1));
    int nowMaxat = maxwhere(num,0,size);
    result[0] = *(num+nowMaxat);
    for(int i =1;i<numLen-size+1;i++){
        if(*(num+size+i-1)<result[i-1] && nowMaxat!=i-1)  result[i] = result[i-1];
        else if(*(num+size+i-1)<result[i-1] && nowMaxat==i-1)  {nowMaxat = maxwhere(num,i,size);result[i] = *(num+nowMaxat);}
        else {nowMaxat = i+size-1;result[i] = *(num+nowMaxat);}
    }
    //for(int i =0;i<numLen-size+1;i++)printf("%d ",*(result+i));
    return result;
}

C 解法, 执行用时: 25ms, 内存消耗: 2724KB, 提交时间: 2022-02-10

/**
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @param size int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int get_max_idx(int *num, int len) {
    int i, ret_i = 0;
    for (i = 0; i < len; i++) {
        if (num[ret_i] < num[i])
            ret_i = i;
    }
    return ret_i;
}


int* maxInWindows(int* num, int numLen, int size, int* returnSize) {
    if (numLen < size || 0 == size) {
        *returnSize = 0;
        return NULL;
    }
    if (1 == size) {
        *returnSize = numLen;
        return num;
    }
    *returnSize = numLen - size + 1;
    int *ret_data = (int *)malloc(sizeof(int) * (*returnSize));
    int s_i = 0, e_i = size, m_i = 0, i;
    m_i = s_i + get_max_idx(&num[s_i], size);
    ret_data[s_i]= num[m_i];
    for (i = e_i; i < numLen; i++) {
        if (m_i == s_i) {
            m_i = get_max_idx(&num[s_i + 1], size) + s_i + 1;
        } else if (num[i] > num[m_i]){
            m_i = i;
        }
        ret_data[++s_i]= num[m_i];
    }
    return ret_data;
}

C 解法, 执行用时: 26ms, 内存消耗: 2640KB, 提交时间: 2022-04-14

/**
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @param size int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int cmp(const void *a, const void *b) {
    int *x = (int *)a;
    int *y = (int *)b;
    return *y - *x;
}
#define INF (1<<30)
typedef struct max {
    int val;
    int idx;
}max_t;

void update_max_idx(int *arr, int l, int r, max_t *max)
{
    max->val = arr[l];
    max->idx = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] >= max->val) {
            max->val = arr[i];
            max->idx = i;
        }
    }
}

int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
    if ((size > numLen) || (size == 0)) {
        *returnSize = 0;
        return NULL;
    }
    *returnSize = numLen - size + 1;
    int *ret = (int *)malloc((*returnSize) * sizeof(int));
    max_t max = {-INF, -1};
    update_max_idx(num, 0, size - 1, &max);
    ret[0] = max.val;
    int count = 1;
    for (int i = size; i < numLen; i++) {
        if (i - max.idx >= size) {
            update_max_idx(num, i - size + 1, i, &max);
            ret[count] = max.val;
            count++;
            continue;
        }
        if (num[i] >= max.val) {
            max.idx = i;
            max.val = num[i];
        }
        ret[count] = max.val;
        count++;
    }
    return ret;
}

详情