本文主要是介绍力扣最热一百题——每日温度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Python后面的文章,内容都比较多,但是同时我又想保持每天更新的速度,所以Python的文章我继续打磨打磨,先更新一篇算法的文章。
一身正气报国家,旁无乱境不恋她
ヾ(◍°∇°◍)ノ゙
力扣题号:739. 每日温度 - 力扣(LeetCode)
下述题目描述和示例均来自力扣
题目描述
给定一个整数数组
temperatures
,表示每天的温度,返回一个数组answer
,其中answer[i]
是指对于第i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用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 <= 105
30 <= temperatures[i] <= 100
上嘴脸!!!!
思路
Java解法一:直接暴力
这里直接两层for循环挨个找就行
class Solution {public int[] dailyTemperatures(int[] temperatures) {int length = temperatures.length;int[] answer = new int[length];for (int i = 0; i < length; i++) {int far = 1;for (int j = i + 1; j < length; j++) {if (temperatures[i] < temperatures[j]){answer[i] = far;break;}else {far++;}}}return answer;}
}
但是不好意思,超时了
因为没过我就不提供另外的语法了
Java解法二:栈
这里我们可以采用一个栈,来记录之前的温度(记录的是低温),然后遍历数组,发现如果今天的温度大于栈顶存储的温度,则将今天温度的数组下标和栈顶的相减获得天数差值,然后存入answer数组即可。
class Solution {public int[] dailyTemperatures(int[] temperatures) {public int[] dailyTemperatures(int[] temperatures) {// 记录数组长度int length = temperatures.length;// 准备需要返回的数组int[] answer = new int[length];// 准备一个栈来存储Deque<Integer> stack = new LinkedList<>();for (int i = 0; i < length; i++) {// 获取每次的温度int temperature = temperatures[i];// 若栈不为空而且,当前温度大于栈顶的温度(这里会一直查找)弹出栈,获取下标差值while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {// 获取栈顶元素int preIndex = stack.pop();// 取得下标差值,写入answer数组answer[preIndex] = i - preIndex;}// 存入栈stack.push(i);}return answer;}
}
C++解法二:栈
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int length = temperatures.size();vector<int> answer(length);stack<int> stack;for(int i = 0; i < length; i++){int temperature = temperatures[i];while(!stack.empty() && temperature > temperatures[stack.top()]){int preIndex = stack.top();answer[preIndex] = i - preIndex;stack.pop();}stack.push(i);}return answer;}
};
对于C++比Java算法题跑的慢这个事情我已经习以为常了。
Python解法二:栈
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:length = len(temperatures)# python的列表初始化answer= [0] * lengthstack = []for i in range(length):temperature = temperatures[i]while stack and temperature > temperatures[stack[-1]]:prev_index = stack.pop()answer[prev_index] = i - prev_indexstack.append(i)return answer
果然是发展越来越好的语言,速度越来越快了奥!
结语
就这样
再见ヾ( ̄▽ ̄)Bye~Bye~
这篇关于力扣最热一百题——每日温度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!