Leetcode hot100 每日温度【中等】

法一动态规划直觉就是用动态规划。既然是动态规划分两步第一步是定义dp问题第二步是推导dp公式。step01: 定义dp问题。很简单刚刚好就是原题要的逻辑。dp[i]记录第一个比第i天高的温度要往后数几天。step02dp公式怎么推呢找几个温度脑子演练一下就推出来了。比如这个例子[78,76,73,74,75,77][ 0, 4, 1, 1, 1, 0]76如何得出4就能拼出dp[i](j-i)以及下标的传递逻辑jjdp[j];78如何得出0假如今天是第i天首先大的值肯定在后面对吧那么最先遍历的肯定是第i1天如果第i1天就比第i天高那么dp[i](i1)-i1不用往后找了。如果低于或等于呢那下一个要比对的不是i2而是去对比第一个比第i1天温度高的也就是第i1dp[i]天同时也是第i天后面所有温度里第一个比第i1天高的这样想就明白了——不会“跳过去第1高的去找第2高的”。如果传递式寻找的过程中遇到了dp[j]0那么不用往下传递了dp[i]0。class Solution { public int[] dailyTemperatures(int[] temperatures) { //初始化 int[] dpnew int[temperatures.length]; dp[temperatures.length-1]0; for(int itemperatures.length-2;i0;i--){ int ji1; //从i1天开始尝试找下一个最大值 while(jtemperatures.length-1){ //1.第j日的温度第i日的温度相当于找到了 if(temperatures[j]temperatures[i]){ //找到了退出循环 dp[i](j-i); break; //2.第j日的温度第i日的温度 }else{ //2.1 第j日以后没有更高的温度了 if(dp[j]0){ //确认找不到了退出循环 dp[i]0; break; } //2.2 第j日以后还有更高的温度 jjdp[j]; //下标传递式寻找类似于“依赖的依赖” } } } return dp; } }法二单调栈这个题在leetcode被划入了单调栈的分类里所以借此机会学一下单调栈。单调栈 始终保持栈内元素单调递增 或 单调递减 的栈。单调栈最大价值快速找「左边 / 右边 第一个比自己大 / 小的元素」正好对应这个题。单调递减栈的规则当前元素栈顶元素满足递减入栈当前元素栈顶元素弹出栈顶元素.继续比较下一个栈顶元素直到栈顶元素当前元素或者栈空class Solution { public int[] dailyTemperatures(int[] temperatures) { int length temperatures.length; int[] result new int[length]; //栈里存的是temperatures的下标而不是温度 DequeInteger st new LinkedList(); //初始化 st.push(0); int i1; while(ilength){ if(temperatures[i]temperatures[st.peek()]){ st.push(i); }else{ while(!st.isEmpty()temperatures[st.peek()]temperatures[i]){ int jst.peek(); result[j]i-j; st.pop(); } st.push(i); } i; } //最后栈里剩下的都是没有比他们大的挨个置0 while(!st.isEmpty()){ result[st.pop()]0; } return result; } }