估且不論執行速度
竟然比之前寫的都快都正確！(是和我個人比起來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;
}
