思路一:按部就班的去模拟单调栈
这样可能会造成时间超时,这里的做法差一个大大数据没有过。
分结果讨论,小于栈顶元素的时候怎么做,大于栈顶元素的时候怎么做;
其中当栈顶元素大于要遍历的元素的时候,我们就需要接着往后进行遍历,也就是在第一重循环的基础上再次遍历后面的数组有没有还小于的,直到我们找到再一次能够小于当前栈顶元素的值。
如果说后面没有小于栈顶元素的值了,我们就应该输入0.如果不是,我们就按照前面遍历的元素个数(包括这个小于栈顶元素)直接放入结果数组中就行了。不要忘记在遍历完之后需要出栈当前元素并更新入栈这个元素。
当我们的栈顶元素小于当前元素的时候,我们就直接进行出栈操作就行了。再次记录栈中的元素有多少个就行了,也就是距离天数。
最后汇总就行了。
class Solution {public int[] dailyTemperatures(int[] temperatures) {Deque<Integer>stk=new LinkedList<>();int []res=new int[temperatures.length];stk.push(temperatures[0]);int cnt=0;int k=0;for(int i=1;i<temperatures.length;i++){if(temperatures[i]>stk.peek()){while(!stk.isEmpty()&&stk.peek()<temperatures[i]){cnt++;stk.pop();}res[k++]=cnt;cnt=0;stk.push(temperatures[i]);}else{int j=i;int counts=0;while(j<temperatures.length&&temperatures[j]<=stk.peek()){counts++;j++;}if(j==temperatures.length){res[k++]=0;}else{res[k++]=counts+1;counts=0;}stk.pop();stk.push(temperatures[i]);}}return res;}
}
思路二:其实和上面的思路大体上相同,但是唯一不一样的地方就是,我们上一个思路中的做法栈中存储的是元素值本身,这个思路中使用了栈元素为下标的值。
同时作者忽略了单调栈的性质问题。其实上面说的那两种情况是没有必要去分类讨论的。
我们还是沿着刚刚的思路进行解法:
当我们碰到栈顶元素小于当前遍历元素的时候,我们就取出其中的坐标,然后跟当前的遍历的元素的下标相减,其实就是这个栈顶元素距离比它还高温度的天数了。我们把这两个操作合起来其实就是下面的答案了。
class Solution {public int[] dailyTemperatures(int[] temperatures) {Deque<Integer>stk=new LinkedList<>();int []res=new int[temperatures.length];for(int i=0;i<temperatures.length;i++){while(!stk.isEmpty()&&temperatures[i]>temperatures[stk.peek()]){int pre=stk.pop();res[pre]=i-pre;}stk.push(i);}return res;}
}