[239] Sliding Window Maximum

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;

}

[20251004]

喔我竟然有回來把hard TBC清掉的一天XD

驀然回首發現我前面兩次寫的都是暴力解啊哈哈哈哈哈跟Monotonic Queue + dequeue一點關係都沒有啊～～～～（國劇甩頭）

還有什麼priority queue是不是，那根本是用C 沒辦法寫的東西啊！

C++真是太偷吃步了，怎麼可以這樣！！！

至於DP (?) 什麼左邊算過來右邊算過來 我實在是看不懂Orz

就來句當年的, 有想到再來冥想看它是怎麼回事XDDDD 以上.

/**

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

*/

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

*returnSize = numsSize -k +1;

if (k==1)

return nums;

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

ret[0]=nums[0];

int *m_stack= calloc (numsSize, sizeof(int));

int top = -1;

int dequeue=-1;

m_stack[++top] = 0; //index

int idx=0;

int movehead=top;

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

{

if (i>=k) // check dequeue

{

#if 1

if (i- m_stack[movehead] >=k)

movehead++;

#else

if (i- m_stack[0] >=k) //會超時的依序copy

{

for (int j=0; j< top;j++)

m_stack[j]=m_stack[j+1];

top--;

}

#endif

}

//insert to m_stack

while (top>=movehead && nums[i]> nums[m_stack[top]])

top--;

m_stack[++top] = i;

if (i >= k-1)

{

ret[idx++]=nums[m_stack[movehead]];

}

}

return ret;

}