hot100-58每日温度

一、题目

给定一个整数数组，表示每天的温度，返回一个answer。

其中answer[i]对于第i天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，该位置为0。

二、思路

1、维护一个递减的单调栈，栈中存放的是温度的下标，维护栈中对应的温度值从栈底到栈顶单调递减。

2、遍历每一天，如果当前温度高于栈顶日期温度，说明找到了更暖的一天。填answer数组：弹出栈顶，计算等待天数，当前天-栈顶天，重复此过程，直到栈空或当前温度小于等于栈顶温度。

将当前天下标入栈。（用栈记住“还在等待更暖天气”的日子，一旦遇到高温，就批量结算答案）

三、代码

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

四、单调栈

单调栈是一种特殊的栈，其中元素（通常是数组的下标）按照其对应的值始终保持单调递增或单调递减的顺序。

用单调栈找下一个更大元素/更小元素。

在入栈前，不断弹出比当前元素小的栈顶，直到栈空或栈顶 ≥ 当前值，再入栈。这样就保证了栈中始终是递减的。