首页 > 其他分享 >LeetCode 739.每日温度(中等)

LeetCode 739.每日温度(中等)

时间:2022-11-25 13:38:24浏览次数:54  
标签:示例 int 中等 栈顶 stack temperatures 739 LeetCode 温度

题目描述:

请根据每日 ​​气温​​​ 列表 ​​temperatures​​​ ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 ​​0​​ 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示:

  • 1 <= temperatures.length <=
  • 30 <= temperatures[i] <= 100

题目分析:

这道题考察单调栈的知识,使用单调栈解决这道题很方便。首先,我们创建一个栈作为单调栈,因为题目要求的是升温的天数,而不是升温后的温度,因此栈中应该存储下标,而非温度。然后从左向右遍历每日温度,若栈为空或者当日温度小于等于栈顶温度则直接入栈。否则,若当日温度大于栈顶温度,说明栈顶元素的升温日已经找到了,则将栈顶元素出栈,计算其与当日相差的天数即可。

题解:

执行用时: 32 ms

内存消耗: 47.8 MB

class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// 获取天数
int n = temperatures.length;
// 结果数组
int[] res = new int[n];
// 单调栈
Stack<Integer> stack = new Stack<>();
// 循环遍历每日温度数组
for (int i = 0; i < n; ++i) {
// 当栈非空
while (!stack.empty()) {
// 获取栈顶元素值
int index = stack.peek();
// 如果当前温度 小于等于 栈顶温度
if (temperatures[i] <= temperatures[index]) {
// 退出循环
break;
}
// 否则弹出栈顶元素
stack.pop();
// 并把日期差填入结果数组相应位置上
res[index] = i - index;
}
// 栈为空就把当前日期压入栈中
stack.push(i);
}
// 返回结果数组
return res;
}
}

题目来源:力扣(LeetCode)



标签:示例,int,中等,栈顶,stack,temperatures,739,LeetCode,温度
From: https://blog.51cto.com/u_15891283/5886560

相关文章

  • LeetCode 20.有效的括号(简单)
    题目描述:给定一个只包括​​'('​​​,​​')'​​​,​​'{'​​​,​​'}'​​​,​​'['​​​,​​']'​​​ 的字符串​​s​​,判断字符串是否有效。有效字符串需满足:......
  • LeetCode 155.最小栈(简单)
    题目描述:设计一个支持​​push​​​,​​pop​​​,​​top​​操作,并能在常数时间内检索到最小元素的栈。​​push(x)​​——将元素x推入栈中。​​pop()​​ —......
  • LeetCode 769.最多能完成排序的块(中等)
    题目描述:数组​​arr​​​是​​[0,1,...,arr.length-1]​​的一种排列,我们将这个数组分割成几个“块”,并将这些块分别进行排序。之后再连接起来,使得连接的结果......
  • LeetCode 240.搜索二维矩阵II(中等)
    题目描述:编写一个高效的算法来搜索 ​​m x n​​​ 矩阵​​matrix​​​中的一个目标值​​target​​。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的......
  • LeetCode 232.用栈实现队列(简单)
    题目描述:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(​​push​​​、​​pop​​​、​​peek​​​、​​empty​​):实现​​MyQueu......
  • LeetCode 448.找到所有数组中消失的数字(简单)
    题目描述:给你一个含​​n​​​个整数的数组​​nums​​​,其中​​nums[i]​​​在区间​​[1,n]​​​内。请你找出所有在​​[1,n]​​​范围内但没有出现......
  • LeetCode 48.旋转图像(中等)
    题目描述:给定一个​​n × n​​​的二维矩阵 ​​matrix​​​表示一个图像。请你将图像顺时针旋转​​90​​度。你必须在原地旋转图像,这意味着你需要直接修改......
  • LeetCode 260.只出现一次的数字III(中等)
    题目描述:给定一个整数数组​​nums​​,其中恰好有两个元素只出现一次,其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。进阶:你的算法......
  • LeetCode 476.数字的补数(简单)
    题目描述:给你一个正整数​​num​​,输出它的补数。补数是对该数的二进制表示取反。示例1:输入:num=5输出:2解释:5的二进制表示为101(没有前导零位),其补数为010。所以......
  • LeetCode 693.交替位二进制数(简单)
    题目描述:给定一个正整数,检查它的二进制表示是否总是0、1交替出现:换句话说,就是二进制表示中相邻两位的数字永不相同。示例1:输入:n=5输出:true解释:5的二进制表示是:101示......