每日温度

题目要求

你需要编写一个函数，该函数接收一个整数数组 temperatures 作为参数，这个数组中的每个元素代表每一天的气温。你的任务是返回一个新的整数数组 answer。对于 answer 中的每个元素 answer[i]，它应该表示从第 i 天开始，要经过多少天才会出现更高的气温。如果从第 i 天开始之后没有任何一天的气温比第 i 天高，那么 answer[i] 应该被设置为 0。

解题思路

要解决这个问题，我们可以采用一个单调栈的数据结构来优化我们的搜索过程。单调栈是一种特殊的栈，用于处理下一个更大或更小元素的问题。在这个问题中，我们需要找到每个元素右边第一个更大的元素的位置。

1. 创建一个栈，用于存储那些还没有找到下一个更高温度的天数的索引。
2. 创建一个数组 answer，初始化为与 temperatures 相同长度的数组，并将所有元素初始化为 0。
3. 遍历 temperatures 数组，对于每一天：
   • 当栈不为空，并且当前天的温度大于栈顶索引对应的温度时，说明我们找到了栈顶索引天数的下一个更高温度。
   • 弹出栈顶元素，将当前天的索引与栈顶索引相减，得到的差值就是两天之间的距离，将这个差值赋值给 answer 数组对应栈顶索引的位置。
   • 重复上述过程，直到栈为空或者当前天的温度不再大于栈顶索引对应的温度。
   • 将当前天的索引压入栈中。
4. 遍历完成后，栈中剩余的索引对应的天数都是没有更高温度的，它们在 answer 数组中已经默认为 0。
5. 返回填充完毕的 answer 数组。

这种方法的时间复杂度是 O(n)，因为每个元素最多被压入和弹出栈一次。空间复杂度也是 O(n)，用于存储栈和结果数组。

Golang 版本

package main

import "fmt"

func dailyTemperatures(temperatures []int) []int {
    length := len(temperatures)
    answer := make([]int, length)
    stack := []int{} // 使用切片模拟栈

    for i, temp := range temperatures {
        for len(stack) > 0 && temp > temperatures[stack[len(stack)-1]] {
            prevIndex := stack[len(stack)-1]
            answer[prevIndex] = i - prevIndex
            stack = stack[:len(stack)-1] // 弹出栈顶元素
        }
        stack = append(stack, i) // 当前索引入栈
    }

    // 栈中剩余的索引对应的天数都是没有更高温度的，它们在answer数组中已经默认为0
    return answer
}

func main() {
    temperatures := []int{73, 74, 75, 71, 69, 72, 76, 73}
    fmt.Println(dailyTemperatures(temperatures))
}

这段代码定义了一个 dailyTemperatures 函数，它接受一个整数切片 temperatures 作为输入，并返回一个整数切片作为输出，表示每天之后多少天会有更高的温度。在 main 函数中，我们给出了一个示例输入，并打印出了函数的输出结果。

C++版本

#include <iostream>
#include <vector>
#include <stack>

std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
    std::vector<int> answer(temperatures.size(), 0);
    std::stack<int> indexStack; // 使用栈来存储索引

    for (int i = 0; i < temperatures.size(); ++i) {
        while (!indexStack.empty() && temperatures[i] > temperatures[indexStack.top()]) {
            int prevIndex = indexStack.top();
            answer[prevIndex] = i - prevIndex;
            indexStack.pop();
        }
        indexStack.push(i);
    }

    // 栈中剩余的索引对应的天数都是没有更高温度的，它们在answer数组中已经默认为0
    return answer;
}

int main() {
    std::vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
    std::vector<int> answer = dailyTemperatures(temperatures);

    for (int temp : answer) {
        std::cout << temp << " ";
    }
    std::cout << std::endl;

    return 0;
}

这段 C++代码实现了与 Golang 版本相同的功能。它定义了一个 dailyTemperatures 函数，该函数接受一个整数向量 temperatures 作为输入，并返回一个整数向量作为输出，表示每天之后多少天会有更高的温度。在 main 函数中，我们给出了一个示例输入，并打印出了函数的输出结果。

Python 版本

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    stack = []  # This will store the indices of the temperatures

    for i, temp in enumerate(temperatures):
        while stack and temp > temperatures[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index
        stack.append(i)

    return answer

# Example usage:
if __name__ == "__main__":
    temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
    print(dailyTemperatures(temperatures))

这段 Python 代码提供了一个 dailyTemperatures 函数，它接受一个温度列表作为输入，并返回一个整数列表作为输出，表示每天之后多少天会有更高的温度。在 if __name__ == "__main__": 部分，我们给出了一个示例输入，并打印出了函数的输出结果。

Java 版本

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>(); // 使用栈来存储索引

        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }

        // 栈中剩余的索引对应的天数都是没有更高温度的，它们在answer数组中已经默认为0
        return answer;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] answer = solution.dailyTemperatures(temperatures);
        System.out.println(Arrays.toString(answer));
    }
}

这段 Java 代码实现了与前面提到的其他语言版本相同的功能。它定义了一个 Solution 类，其中包含一个 dailyTemperatures 方法，该方法接受一个整数数组 temperatures 作为输入，并返回一个整数数组作为输出，表示每天之后多少天会有更高的温度。在 main 方法中，我们创建了 Solution 类的一个实例，并给出了一个示例输入，然后打印出了方法的输出结果。

Rust 版本

fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let mut answer = vec![0; temperatures.len()];
    let mut stack: Vec<usize> = Vec::new();

    for (i, &temp) in temperatures.iter().enumerate() {
        while let Some(&last_index) = stack.last() {
            if temp <= temperatures[last_index] {
                break;
            }
            stack.pop();
            answer[last_index] = (i - last_index) as i32;
        }
        stack.push(i);
    }

    answer
}

fn main() {
    let temperatures = vec![73, 74, 75, 71, 69, 72, 76, 73];
    let answer = daily_temperatures(temperatures);
    println!("{:?}", answer);
}

这段 Rust 代码实现了一个 daily_temperatures 函数，它接受一个 i32 类型的向量 temperatures 作为输入，并返回一个同样是 i32 类型的向量作为输出，表示每天之后多少天会有更高的温度。在 main 函数中，我们给出了一个示例输入，并打印出了函数的输出结果。

总结

上述代码段展示了如何使用不同编程语言（Go, C++, Python, Java, Rust）来解决同一个问题：给定一个表示每天温度的整数数组 temperatures，计算对于每一天，还需要等待多少天才能得到更高的温度。如果不存在这样的未来一天，则对应的结果为 0。

解决方案的核心思想是使用一个栈来跟踪尚未找到更高温度的天数的索引。算法的步骤如下：

1. 初始化一个栈来存储索引，以及一个数组 answer 来存储结果，初始值为 0。
2. 遍历 temperatures 数组，对于每个元素：
   • 当栈不为空且当前温度大于栈顶索引对应的温度时：
     • 弹出栈顶元素，这是一个尚未找到更高温度的天的索引。
     • 计算当前天与栈顶索引对应天的差值，这是等待的天数，将其存储在 answer 数组对应位置。
   • 将当前索引压入栈中。
3. 遍历完成后，栈中剩余的索引对应的天数都是没有更高温度的，它们在 answer 数组中已经默认为 0。

这种方法的时间复杂度通常是 O(n)，因为每个元素最多被压入和弹出栈一次。空间复杂度是 O(n)，用于存储栈和结果数组。

不同语言的实现细节略有不同，但算法逻辑是一致的。例如，Go 使用切片模拟栈，C++ 使用 std::stack，Python 使用列表，Java 使用 Stack 类，而 Rust 使用向量。尽管语法不同，但所有这些实现都遵循了上述算法步骤。