#P4081. 每日温度
-
ID: 2322
Tried: 62
Accepted: 22
Difficulty: 6
-
算法标签>数据结构栈
每日温度
题目内容
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i]是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替
输入描述
一个整数数组 temperatures
输出描述
一个数组 answer
样例1
输入
73 74 75 71 69 72 76 73
输出
1 1 4 2 1 1 0 0
样例2
输入
30 40 50 60
输出
1 1 1 0
样例3
输入
30 60 90
输出
1 1 0
提示：
- 1<=temperatures.length<=105
- 30<=temperatures[i]<=100
题解
题面描述
给定一个整数数组 temperatures，表示每天的温度，要求返回一个数组 answer，其中 answer[i] 表示对于第 i 天，下一个更高温度出现在几天后。如果之后没有比当前温度更高的温度，则 answer[i] 为 0。
思路
- 单调栈思想：
使用单调递减栈来维护温度下标。当遍历到第 i 天温度时，若栈顶对应的温度低于当前温度，则说明对于栈顶的那一天，第 i 天就是它的“下一个更高温度”的日子，因此可以计算出间隔天数并将其赋值给 answer 中相应的位置。
代码分析
- 时间复杂度：
每个下标最多被入栈和出栈一次，因此时间复杂度为 O(n)。 - 空间复杂度：
需要一个栈来存储下标，最坏情况下空间复杂度为 O(n)。
C++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n, 0);
stack<int> st; // 存储温度下标
// 遍历温度数组
for (int i = 0; i < n; i++) {
// 当栈不空且当前温度大于栈顶下标对应的温度时
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
int idx = st.top();
st.pop();
answer[idx] = i - idx; // 计算天数差
}
st.push(i);
}
return answer;
}
};
int main() {
vector<int> temperatures;
int temp;
while (cin >> temp) {
temperatures.push_back(temp);
}
Solution sol;
vector<int> result = sol.dailyTemperatures(temperatures);
// 输出结果
for (int i = 0; i < result.size(); i++) {
cout << result[i];
if(i < result.size() - 1) cout << " ";
}
return 0;
}
Python
class Solution:
def dailyTemperatures(self, temperatures: list) -> list:
n = len(temperatures)
answer = [0] * n # 初始化答案数组
stack = [] # 存储温度下标
# 遍历温度数组
for i in range(n):
# 当栈不空且当前温度大于栈顶下标对应的温度时
while stack and temperatures[i] > temperatures[stack[-1]]:
idx = stack.pop()
answer[idx] = i - idx # 计算天数差
stack.append(i)
return answer
if __name__ == '__main__':
import sys
data = sys.stdin.read().strip().split()
temperatures = list(map(int, data))
sol = Solution()
result = sol.dailyTemperatures(temperatures)
print(" ".join(map(str, result)))
Java
import java.util.*;
import java.io.*;
public class Main {
static 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 idx = stack.pop();
answer[idx] = i - idx; // 计算天数差
}
stack.push(i);
}
return answer;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
String[] tokens = line.trim().split("\\s+");
int n = tokens.length;
int[] temperatures = new int[n];
for (int i = 0; i < n; i++) {
temperatures[i] = Integer.parseInt(tokens[i]);
}
Solution sol = new Solution();
int[] result = sol.dailyTemperatures(temperatures);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
sb.append(result[i]);
if(i < result.length - 1) sb.append(" ");
}
System.out.println(sb.toString());
}
}