[739] Daily Temperatures

照著題意直覺下去寫～果然超時了XD 我就知道不是憨Q想的那麼單純QQ

但我還是要先貼一下...不管效能的話它也是一種答案不是嗎XD（阿Q自我安慰）

/**

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

*/

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {

int *idxStack = calloc(temperaturesSize, sizeof(int));

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

*returnSize = temperaturesSize;

//push the first one

int head = 0;

idxStack[0]= 0;

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

{

//pop and add 1 in ret with all element in stack

while (head>=0 && temperatures[i]> temperatures[idxStack[head]])

{

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

ret[idxStack[j]]++;

head-- ;

}

idxStack[++head] = i;

}

for (int j=0;j<= head;j++) // deal with the rest in stack, never get warmer

ret[idxStack[j]]=0;

return ret;

}

至於偷瞄了一下解答的寫法說是要從後面找回來?! 先讓我想一想QQ

(分隔線)

想完了！但是覺得好像不用stack也可以嗎～我看到別人有用temp 就算完的？XD

不管了先降XD

/**

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

*/

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {

int *idxStack = calloc(temperaturesSize, sizeof(int));

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

*returnSize = temperaturesSize;

int head = 0;

idxStack[0]= temperaturesSize-1;

for (int i=temperaturesSize-2; i >=0; i--)

{

if (temperatures[i] < temperatures[idxStack[head]])

ret[i] = idxStack[head] - i;

else

{

while (head>=0 && temperatures[i] >= temperatures[idxStack[head]])

head--;

ret[i] = (head < 0)? 0 : (idxStack[head] - i);

}

idxStack[++head] = i;

}

return ret;

}