[1438] Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

ㄟ～寫了一個超時（？）不太確定它是不是能動的XD

先留個紀錄在這兒～明天來寫個 雙Queue 版

#define max(A,B) (A>B)?(A):(B)

#define min(A,B) (A<B)?(A):(B)

int longestSubarray(int* nums, int numsSize, int limit) {

int l=0, r=0;

int ret=1;

for (int l=0; l<numsSize; l++)

{

int min = nums[l];

int max = nums[l];

for (int r=l; r<numsSize; r++)

{

int tmp = min(nums[l], nums[r]);

if (tmp < min)

min = tmp;

tmp = max(nums[l], nums[r]);

if (tmp > max)

max = tmp;

int diff = max-min;

if (diff <= limit)

{

if (r-l+1 > ret)

ret = r-l+1;

}

else

{

while (r<numsSize-1)

{

if (nums[r+1]<= max || nums[r+1]>=min)

r++;

}

}

}

}

return ret;

}

一陣亂七八糟之後，有了第二版的超時垃圾 （？）

#define max(A,B) (A>B)?(A):(B)

#define min(A,B) (A<B)?(A):(B)

#define BIG 0

#define SMALL 1

//type = 0: max ; 1:min

void deQueue(int* nums, int *newtop)

{

int len = *newtop;

for (int i=0; i<len; i++)

{

nums[i]= nums[i+1];

}

*newtop = len-1;

return;

}

//type = 0: max ; 1:min

void inQueue(int* nums, int num, int *_top, bool type)

{

int top = *_top;

if (top < 0)

{

nums[++top]= num;

*_top= top;

return;

}

if (type==0)

{

while (top>=0 && nums[top]<num)

top--;

}

else

{

while (top>=0 && nums[top]>num)

top--;

}

nums[++top]= num;

*_top= top;

return;

}

int longestSubarray(int* nums, int numsSize, int limit) {

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

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

int maxIdx=-1;

int minIdx=-1;

int l=0, r=0;

int ret=0;

for (;r<numsSize;r++)

{

inQueue(maxQ, nums[r],&maxIdx,BIG);

inQueue(minQ, nums[r],&minIdx,SMALL);

while (maxQ[0]-minQ[0]>limit)

{

if (nums[l]== maxQ[0])

deQueue(maxQ,&maxIdx);

if (nums[l]== minQ[0])

deQueue(minQ,&minIdx);

l++;

}

ret = max (ret, r-l+1);

}

return ret;

}

終於不超時了，但是世界醜啊～～～～～～～～

我的腦子是不是有洞啊........

#define max(A,B) (A>B)?(A):(B)

#define min(A,B) (A<B)?(A):(B)

#define BIG 0

#define SMALL 1

//type = 0: max ; 1:min

void inQueue(int* nums, int num, int *_top, bool type, int head)

{

int top = *_top;

if (top < 0)

{

nums[++top]= num;

*_top= top;

return;

}

if (type==0)

{

while (top>=head && nums[top]<num)

top--;

}

else

{

while (top>=head && nums[top]>num)

top--;

}

nums[++top]= num;

*_top= top;

return;

}

int longestSubarray(int* nums, int numsSize, int limit) {

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

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

int maxIdx=-1, maxHead = 0;

int minIdx=-1, minHead = 0;

int l=0, r=0;

int ret=0;

for (;r<numsSize;r++)

{

inQueue(maxQ, nums[r],&maxIdx,BIG,maxHead);

inQueue(minQ, nums[r],&minIdx,SMALL,minHead);

while (maxQ[maxHead]-minQ[minHead]>limit)

{

if (nums[l]== maxQ[maxHead])

maxHead++;

if (nums[l]== minQ[minHead])

minHead++;

l++;

}

ret = max (ret, r-l+1);

}

return ret;

}