LeetCode：739. 每日温度

简介题目链接https://leetcode.cn/problems/daily-temperatures/description/解决方式数组 暴力枚举 / 单调栈暴力枚举思路可以直接双重循环。外层循环迭代每一个元素内层循环找到更高的温度。classSolution{publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;int[]answernewint[n];for(inti0;in;i){for(intji1;jn;j){if(temperatures[j]temperatures[i]){answer[i]j-i;// 找到一个直接迭代下一个元素break;}}}// 返回结果returnanswer;}}单调栈思路暴力枚举的方式时间复杂度太高我们可以借助栈实现一次遍历。维护一个单调递减的栈从栈底到栈顶单调递减。迭代每一个元素若当前元素比栈顶元素大说明栈顶元素遇到下一个更高的温度出栈并记录。继续比较新的栈顶与当前迭代元素因为新的栈顶元素比原来的大所以有可能比当前迭代元素大也可能小所以继续比较看看谁大谁小如此循环。classSolution{publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;// 结果集合int[]answernewint[n];// 单调递减栈栈底 - 栈顶DequeIntegerstacknewArrayDeque();// 迭代for(inti0;in;i){// 栈不为空且迭代元素比栈顶元素大则栈顶元素出栈并标记遇到更大温度while(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){// 出栈intpindexstack.pop();// 记录更高温度answer[pindex]i-pindex;}// 迭代元素入栈索引stack.push(i);}// 返回结果returnanswer;}}