如題：

根據(jù)每日 氣溫 列表，請重新生成一個(gè)列表，對應(yīng)位置的輸入是你需要再等待多久溫度才會升高超過該日的天數(shù)。如果之后都不會升高， 請?jiān)谠撐恢糜?0 來代替。例如，給定一個(gè)列表?temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是?[1, 1, 4, 2, 1, 1, 0, 0]。提示：氣溫 列表長度的范圍是?[1, 30000]。每個(gè)氣溫的值的均為華氏度，都是在?[30, 100]?范圍內(nèi)的整數(shù)。

?在leetcode棧的專項(xiàng)練習(xí)遇到這一題，既然是在棧的專項(xiàng)練習(xí)里面，應(yīng)該存在可以用棧的解法，想了一會兒，沒想到。雖然沒想到，但是這題不復(fù)雜，找到每個(gè)數(shù)字后面的第一個(gè)比它大的值，返回距離即可。簡單的順序遍歷即可，對于每個(gè)元素i，遍歷i+1 ~n，找到第一個(gè)大于它的值即可返回，測試該方法可以，但是在存在大量數(shù)據(jù)的時(shí)候，該暴力遍歷法會因?yàn)槌^時(shí)長而失敗。

可以看到，每次遍歷的時(shí)候，我們都需要計(jì)算i和它后面的每一個(gè)值，這樣算太慢了，但是如果我們從后往前逆序遍歷的話，則存在一種優(yōu)化方法，逆序遍歷，如果T[i] < T[i+1]，則可以直接得到i點(diǎn)的值ret[i] = 1，如果T[i] >= T[i+1]，我們不必遍歷i+1 ~n每一個(gè)數(shù)，只需要從 ret[i+1]開始即可，因?yàn)門[ ret[ i+1 ] ]?大于T[i+1]，從i+1到ret[i + 1]之間的數(shù)必定小于T[i+1]，因此可以忽略不去比較，僅和大于T[i+1]的值比較即可。

單調(diào)棧解法，

對于每一個(gè)數(shù)i而言，我們首先比較i和i+1，如果小于它則可以直接得到求解1，如果T[i] >= T[i+1]，這時(shí)候我們需要比較i+1 ~ n，但是，這里我們是沒有必要比較比T[i+1]小的數(shù)，僅需要比較比T[i+1]大的數(shù)即可，這樣可以建立一個(gè)遞減棧，棧中最小元素為T[i+1],棧中元素從頂?shù)降陀行∽兇蟆５慕⒘鞒倘缦?#xff1a;如果棧空，則當(dāng)前節(jié)點(diǎn)入棧，如果棧不空，則與棧頂元素依次比較，將比自己小的元素出棧，最后自己入棧即可，這里棧存儲的是在原溫度數(shù)組中的下標(biāo)，這樣可以直接得到自己所求解。這樣的話，我們可以逆序遍歷溫度數(shù)組，和棧中元素比較，找到比自己第一個(gè)大的值所在下標(biāo)，相減即可，如果找不到，即棧空，這時(shí)候解為0，同時(shí)自己入棧，開始下一個(gè)。該方法減少重復(fù)比較流程和暴力優(yōu)化法類似，還不理解的同學(xué)建議親自擼下代碼試試。

單調(diào)遞減棧 c代碼，前面的代碼為棧的操作部分，可略過不看，僅看末尾核心函數(shù)就可以了。

/*** Note: The returned array must be malloced, assume caller calls free().*/#define STACKSIZE 30000 typedef struct{int top, bottom, length, max;int con[STACKSIZE]; }stack;stack *createStack() {stack *st;st = (stack *)malloc(sizeof(stack));if (!st) return NULL;st->top = st->bottom = st->length = 0;st->max = STACKSIZE;return st; }void initStack(stack *st) {st->top = st->bottom = st->length = 0;st->max = STACKSIZE;return ; }int isStackEmpty(stack *st) {if (st->length == 0)return 1;elsereturn 0; }int isStackFull(stack *st) {if (st->length == STACKSIZE)return 1;elsereturn 0; }int pop(stack *st) {if (st->length == 0)return 0;else{st->length--;st->top--;return st->con[st->top];} }void push(stack *st, int v) {if (isStackFull(st))return;else{st->length++;st->con[st->top++] = v;return;} }int peekStack(stack *st) {return st->con[st->top-1]; }int* dailyTemperatures(int* T, int TSize, int* returnSize){int i, peek, *ret;stack st;*returnSize = TSize;initStack(&st);//特殊情況if (!T || TSize < 1)return NULL;ret = (int *)malloc(sizeof(int) * TSize);if (!ret) exit(1);for (i = TSize - 1; i >= 0; i--){//遍歷棧找比自己大的值while(!isStackEmpty(&st) && T[i] >= T[peekStack(&st)]){pop(&st);}//如果棧空，則表示自己是最大值if (isStackEmpty(&st))ret[i] = 0;elseret[i] = peekStack(&st) - i;push(&st, i);}return ret; }

暴力法優(yōu)化，c代碼：

int* dailyTemperatures(int* T, int TSize, int* returnSize){int i, j, len, *ret;len = *returnSize = TSize;if (!T || TSize < 1)return NULL;ret = (int *)malloc(sizeof(int) * TSize);if (!ret) {printf("malloc error\n");return NULL;}ret[len-1] = 0;for (j = len - 2; j >= 0; j--){ret[j] = 0;i = j + 1;//相比直接得到if (T[j] < T[i])ret[j] = 1;else {//繼續(xù)比較，跳過不必要的比較while (i < len && ret[i] != 0){i += ret[i];if (T[i] > T[j]){ret[j] = i - j;break;}}}}return ret; }

?

=============================================================================================

Linux應(yīng)用程序、內(nèi)核、驅(qū)動開發(fā)交流討論群(745510310)，感興趣的同學(xué)可以加群討論、交流、資料查找等，前進(jìn)的道路上，你不是一個(gè)人奧^_^。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的leetcode 739. 每日温度 单调栈解法和暴力法及其优化 c代码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。