Leetcode hot100 每日温度【中等】

法（一）动态规划

直觉就是用动态规划。既然是动态规划，分两步，第一步是定义dp问题，第二步是推导dp公式。

step01: 定义dp问题。很简单，刚刚好就是原题要的逻辑。dp[i]记录第一个比第i天高的温度要往后数几天。

step02：dp公式怎么推呢？找几个温度，脑子演练一下，就推出来了。

比如这个例子：

[78,76,73,74,75,77]
[ 0, 4, 1, 1, 1, 0]

76如何得出4？就能拼出dp[i]=(j-i)，以及下标的传递逻辑j=j+dp[j];
78如何得出0？

假如今天是第i天，首先大的值肯定在后面对吧，那么最先遍历的肯定是第i+1天，如果第i+1天就比第i天高，那么dp[i]=(i+1)-i=1，不用往后找了。如果低于或等于呢？那下一个要比对的不是i+2，而是去对比第一个比第i+1天温度高的，也就是第i+1+dp[i]天，同时也是第i天后面所有温度里第一个比第i+1天高的，这样想就明白了——不会“跳过去第1高的去找第2高的”。如果传递式寻找的过程中遇到了dp[j]=0，那么不用往下传递了，dp[i]=0。

class Solution { public int[] dailyTemperatures(int[] temperatures) { //初始化 int[] dp=new int[temperatures.length]; dp[temperatures.length-1]=0; for(int i=temperatures.length-2;i>=0;i--){ int j=i+1; //从i+1天开始尝试找下一个最大值 while(j<=temperatures.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日以后还有更高的温度 j=j+dp[j]; //下标：传递式寻找，类似于“依赖的依赖” } } } return dp; } }

法（二）单调栈

这个题在leetcode被划入了单调栈的分类里，所以借此机会学一下单调栈。

单调栈 = 始终保持栈内元素单调递增 或 单调递减 的栈。

单调栈最大价值：快速找「左边 / 右边 第一个比自己大 / 小的元素」，正好对应这个题。

单调递减栈的规则：

当前元素<=栈顶元素，满足递减，入栈

当前元素>栈顶元素，弹出栈顶元素.继续比较下一个栈顶元素，直到栈顶元素<=当前元素或者栈空

class Solution { public int[] dailyTemperatures(int[] temperatures) { int length = temperatures.length; int[] result = new int[length]; //栈里存的是temperatures的下标，而不是温度 Deque<Integer> st = new LinkedList<>(); //初始化 st.push(0); int i=1; while(i<length){ if(temperatures[i]<=temperatures[st.peek()]){ st.push(i); }else{ while(!st.isEmpty()&&temperatures[st.peek()]<temperatures[i]){ int j=st.peek(); result[j]=i-j; st.pop(); } st.push(i); } i++; } //最后栈里剩下的，都是没有比他们大的，挨个置0 while(!st.isEmpty()){ result[st.pop()]=0; } return result; } }