一 题目:
二 思路:
单调栈
这里注意,如果气温在这之后都不会升高,则将该位置用0来代替。
- 根据以上的信息,我们可以先创建一个temperatures等长的全零数组,然后初始化一个栈
- 这里注意由于需要返回相差天数,所以栈中需要保存元素下标来实现天数计算。
- 下来循环temperatures进行栈的操作,循环过程中,持续判断当前下标温度与栈顶下标温度的大小差别
- 如果当前下标的温度大于栈顶下标的温度,表示找到了下一个更大的温度,弹出栈顶下标,计算天数差别,
- 更新res[栈顶下标] = 当前下标 - 栈顶下标
- 否则将当前下标加入栈顶
- res中没有更新的元素,表示未找到更高的温度,最终返回ret即可。
三 代码:
单调栈法
class Solution {
/**
* 单调栈法
* @param temperatures
* @return
*/
public int[] dailyTemperatures(int[] temperatures) {
//存储没找到更高温度的下标
Stack<Integer> stack=new Stack<>();
//结果集
int[] res=new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[I]){
Integer index = stack.pop();
res[index]=i-index;
}
stack.push(i);
}
return res;
}
}
网友评论