题解

题面描述

给定一个整数数组 $temperatures$，表示每天的温度，要求返回一个数组 $answer$，其中 $answer[i]$ 表示对于第 $i$ 天，下一个更高温度出现在几天后。如果之后没有比当前温度更高的温度，则 $answer[i]$ 为 $0$。

思路

1. 单调栈思想：
   使用单调递减栈来维护温度下标。当遍历到第 $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());
    }
}

Leetcode 72.每日温度-原题链接

题目内容

给定一个整数数组 $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 <= 10^5$
• $30 <= temperatures[i] <= 100$