[239] Sliding Window Maximum （TBC)

Hard程度的題目！
估且不論執行速度
竟然比之前寫的都快都正確！(是和我個人比起來Orz）
感動 ！！！！！！

就是說給一個array, 還有一個長度k的window
當這個window由左至右滑動時
記錄下當時window裡的最大值
回傳這組最大值.

Sliding Window Maximum

/**

 * Return an array of size *returnSize.

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

 */

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {

    if(nums == NULL || numsSize==0)

        return NULL;

    *returnSize = (numsSize -k)+1;

    int* ret = malloc(sizeof(int)*(*returnSize));

    int max=0;

    

    for(int i=0;i<(*returnSize);i++)

    {

        max=nums[i];

        for (int s=i;s<i+k;s++)

        {

            if(nums[s]> max)

                max = nums[s];

        }

        ret[i]=max;

    }

    return ret;

}

據說正解是什麼Sliding Window Minimum / Monotonic Queue的

但不知道為什麼現在無法思考 囧

睡前再來冥想看它是怎麼回事

先降～（揮手下降）

20240714 update

發現以前寫的，以現在的測資去測根本就會超時啊哈哈哈哈哈XDDDD

怎麼會這樣= =+ 

重新寫的以為有加到速，看來是沒有 XD 但還是先貼一下

會不會再回來寫Monotonic Queue , let's wait and see XD

int findMax (int* nums, int start, int end, int numsSize)

{

int ret = INT_MIN;

for (int i=start; i <= end;i++)

{

if (nums[i]>ret)

ret= nums[i];

}

return ret;

}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {

*returnSize = numsSize-k+1;

int *ret = calloc (*returnSize, sizeof(int));

if (k==1)

return nums;

int tmpMax = findMax(nums, 0, k-1, numsSize);

int idx=0;

ret[idx] = tmpMax; // we will increse idx later: after use it as left pointer

for (int i=k;i<numsSize;i++)

{

int new = nums[i];

int oldMax = ret[idx];

if (new <oldMax && nums[idx]!= oldMax)

ret[++idx] = oldMax;

else if (new >oldMax)

ret[++idx] = new;

else //(new <oldMax && nums[k]== oldMax)

ret[++idx] = findMax(nums, idx, idx+k, numsSize);

}

return ret;

}