LeetCode：739. 每日温度

简介

题目链接：https://leetcode.cn/problems/daily-temperatures/description/

解决方式：数组 + 暴力枚举 / 单调栈

暴力枚举

思路：可以直接双重循环。外层循环迭代每一个元素，内层循环找到更高的温度。

classSolution{publicint[]dailyTemperatures(int[]temperatures){intn=temperatures.length;int[]answer=newint[n];for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){if(temperatures[j]>temperatures[i]){answer[i]=j-i;// 找到一个直接迭代下一个元素break;}}}// 返回结果returnanswer;}}

单调栈

思路：暴力枚举的方式时间复杂度太高，我们可以借助栈实现一次遍历。维护一个单调递减的栈，从栈底到栈顶单调递减。迭代每一个元素，若当前元素比栈顶元素大，说明栈顶元素遇到下一个更高的温度，出栈并记录。继续比较新的栈顶与当前迭代元素，因为新的栈顶元素比原来的大，所以有可能比当前迭代元素大，也可能小，所以继续比较，看看谁大谁小，如此循环。

classSolution{publicint[]dailyTemperatures(int[]temperatures){intn=temperatures.length;// 结果集合int[]answer=newint[n];// 单调递减栈（栈底 -> 栈顶）Deque<Integer>stack=newArrayDeque<>();// 迭代for(inti=0;i<n;i++){// 栈不为空且迭代元素比栈顶元素大，则栈顶元素出栈并标记遇到更大温度while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){// 出栈intpindex=stack.pop();// 记录更高温度answer[pindex]=i-pindex;}// 迭代元素入栈（索引）stack.push(i);}// 返回结果returnanswer;}}