乌鲁木齐市网站建设_网站建设公司_GitHub_seo优化

题目描述：

思路分析（单调栈）

这道题最优解是使用单调栈（Monotonic Stack）。

核心思想：

• 我们从左到右遍历每一天。
• 用一个栈来维护一个从栈底到栈顶温度严格递减的索引序列（即栈中保存的是还没有找到更高温度的日子）。
• 当遇到一个新温度时，如果它比栈顶那天的温度高，说明栈顶那天“等到了”更暖和的一天，就可以弹出栈顶，计算等待天数。
• 不断弹出，直到栈顶温度不低于当前温度，或者栈为空。
• 最后把当前天的索引入栈，继续等待未来的更高温度。

为什么是 O(n)？

• 每个元素最多入栈一次、出栈一次，总操作次数是 O(n)，非常高效。

代码：

class Solution { public int[] dailyTemperatures(int[] temperatures) { int n=temperatures.length; Stack<Integer> stack =new Stack<>(); int[] res=new int[n]; for(int i=0;i<n;i++){ while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){ int a=stack.pop(); res[a]=i-a; } stack.push(i); } res[n-1]=0; return res; } }