leetcode 739. 每日温度 单调栈解法和暴力法及其优化 c代码

如题：

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高， 请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

 在leetcode栈的专项练习遇到这一题，既然是在栈的专项练习里面，应该存在可以用栈的解法，想了一会儿，没想到。虽然没想到，但是这题不复杂，找到每个数字后面的第一个比它大的值，返回距离即可。简单的顺序遍历即可，对于每个元素i，遍历i+1 ~n，找到第一个大于它的值即可返回，测试该方法可以，但是在存在大量数据的时候，该暴力遍历法会因为超过时长而失败。

可以看到，每次遍历的时候，我们都需要计算i和它后面的每一个值，这样算太慢了，但是如果我们从后往前逆序遍历的话，则存在一种优化方法，逆序遍历，如果T[i] < T[i+1]，则可以直接得到i点的值ret[i] = 1，如果T[i] >= T[i+1]，我们不必遍历i+1 ~n每一个数，只需要从 ret[i+1]开始即可，因为T[ ret[ i+1 ] ] 大于T[i+1]，从i+1到ret[i + 1]之间的数必定小于T[i+1]，因此可以忽略不去比较，仅和大于T[i+1]的值比较即可。

单调栈解法，

对于每一个数i而言，我们首先比较i和i+1，如果小于它则可以直接得到求解1，如果T[i] >= T[i+1]，这时候我们需要比较i+1 ~ n，但是，这里我们是没有必要比较比T[i+1]小的数，仅需要比较比T[i+1]大的数即可，这样可以建立一个递减栈，栈中最小元素为T[i+1],栈中元素从顶到低有小变大。栈的建立流程如下：如果栈空，则当前节点入栈，如果栈不空，则与栈顶元素依次比较，将比自己小的元素出栈，最后自己入栈即可，这里栈存储的是在原温度数组中的下标，这样可以直接得到自己所求解。这样的话，我们可以逆序遍历温度数组，和栈中元素比较，找到比自己第一个大的值所在下标，相减即可，如果找不到，即栈空，这时候解为0，同时自己入栈，开始下一个。该方法减少重复比较流程和暴力优化法类似，还不理解的同学建议亲自撸下代码试试。

单调递减栈 c代码，前面的代码为栈的操作部分，可略过不看，仅看末尾核心函数就可以了。

/*** 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; }

暴力法优化，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 {//继续比较，跳过不必要的比较while (i < len && ret[i] != 0){i += ret[i];if (T[i] > T[j]){ret[j] = i - j;break;}}}}return ret; }

 

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

Linux应用程序、内核、驱动开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的leetcode 739. 每日温度 单调栈解法和暴力法及其优化 c代码的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。