代码随想录算法| 单调栈、739. 每日温度

本文主要是介绍代码随想录算法| 单调栈、739. 每日温度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

单调栈

单调栈的单调体现在栈里的元素需要是递增或递减（栈头到栈尾，头进头出）的。

单调栈的使用场景通常是一维数组，要寻找任一元素的右边或者左边第一个比自己大或者小的元素的位置。

单调栈中通常存放的不是元素，而是元素下标，因为通过元素下标可以轻松得到元素值，但元素值无法直接得到下标。

至于栈中元素到底是递增还是递减，取决于具体场景。如果是求元素右边第一个比自己大的元素的位置，应该递增；如果求元素右边第一个比自己小的元素的位置，应该递减。

739. 每日温度

完成

思路：

暴力解法很容易想到，两层for循环，使用单调栈可以用空间换时间。

单调栈中存放遍历过的元素，与当前元素比较，得出当前元素比之前遍历过的某个元素大。这样就可以省掉一层for循环，一次遍历即可。

准确来说，单调栈中存放的是之前遍历过的，且还没找到右边第一个比自己大的元素的下标。在遍历过程中，如果当前元素比栈顶元素大，说明栈顶元素找到了目标，此时就可以出栈了(如果新的栈顶元素仍然满足条件也可以出栈)，然后当前元素入栈。

也就是说当前元素入栈时，会把栈中所有比自己小的元素先出栈，这样就保持了单调性。

代码

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];// 单调栈，存放元素下标LinkedList<Integer> stack = new LinkedList<>();// 注意这里不能用addstack.push(0);for (int i = 1; i < temperatures.length; i++) {if(temperatures[i]<=temperatures[stack.peek()]){stack.push(i);}else{while (!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]) {res[stack.peek()] = i-stack.peek();stack.pop();}stack.push(i);}}return res;}
}