leetcode739：每日温度

题目链接

leetcode

题目描述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void printArray(vector<int>& arr) {
	for (auto x : arr) {
		cout << x << " ";
	}
	cout << endl;
}

/*
    根据题目可知，是找下一个更大元素。
    此处不是求下一个更大元素的值是多少，而是当前元素与下一个更大元素的索引距离。
    因此，直接使用单调栈的算法模板，维护一个单调栈来存储温度列表中的下标。

    单调栈的核心在于维护栈内的元素单调性，即在栈内元素保持单调递增或单调递减。
    对于“下一个更大元素”问题，希望栈内元素是单调递减的，
    这样新入栈的元素（即当前遍历到的元素）可以与栈内所有元素（之前遍历过的元素）进行比较，
    以找到下一个更大的元素。

    时间复杂度：O(n)
        其中 n 是温度列表的长度。
        遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。
    空间复杂度：O(n)
        在最坏情况下，所有元素都可能被压入栈中，栈的空间消耗为 O(n)。
        结果数组的空间消耗也是 O(n)。
*/
class Solution_0 {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0); // 结果数组
        stack<int> stk;        // 栈中存储元素的下标

        // 倒着存入栈中
        for (int i = n - 1; i >= 0; i --) {
            while (!stk.empty() && temperatures[i] >= temperatures[stk.top()]) {
                stk.pop();
            }
            // 计算下标间距
            res[i] = stk.empty() ? 0 : (stk.top() - i);
            // 元素的下标入栈
            stk.push(i);
        }

        return res;
    }
};

/*
    思路同上
*/
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0); // 结果数组
        stack<int> stk;        // 栈中存储元素的下标

        for (int i = 0; i < n; i ++) {
            // 保证栈内元素的单调递减性质
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                int index = stk.top(); stk.pop();
                res[index] = i - index;
            }
            stk.push(i);
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
    printArray(temperatures);
    vector<int> result = solution.dailyTemperatures(temperatures);
    cout << "Days to get warmer: ";
    for (int day : result) {
        cout << day << " ";
    }
    cout << endl; // 应该输出 "0 1 1 4 2 1 0 0"

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   栈的使用：
       使用一个栈来存储温度数组的索引。
       遍历温度数组，对于每个温度：
           如果当前温度大于栈顶索引对应的温度，则更新结果数组，并弹出栈顶索引。
           当前索引入栈。
   结果数组：
       初始化结果数组 result，所有值默认为 0。
       对于每个温度，如果找到了更高的温度，则更新 result 中对应的天数。

    时间复杂度：O(n)
        每个温度最多入栈和出栈一次，因此时间复杂度为 O(n)，其中 n 是温度数组的长度。
    空间复杂度：O(n)
        使用了一个栈来存储索引，空间复杂度为 O(n)。
*/
// dailyTemperatures 返回每天之后需要等待的天数，直到温度升高
func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures)
	result := make([]int, n) // 初始化结果数组，所有值默认为 0
	stack := []int{}         // 使用栈存储索引

	for i := 0; i < n; i ++ {
		// 当前温度大于栈顶索引对应的温度时，更新结果
		for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1] // 弹出栈顶
			result[top] = i - top       // 更新天数
		}
		stack = append(stack, i) // 当前索引入栈
	}

	return result
}

func main() {
	// 测试用例
	testCases := []struct {
		temperatures []int
		expected     []int
	}{
		{
			temperatures: []int{73, 74, 75, 71, 69, 72, 76, 73},
			expected:     []int{1, 1, 4, 2, 1, 1, 0, 0},
		},
		{
			temperatures: []int{30, 40, 50, 60},
			expected:     []int{1, 1, 1, 0},
		},
		{
			temperatures: []int{30, 60, 90},
			expected:     []int{1, 1, 0},
		},
	}

	for i, tc := range testCases {
		result := dailyTemperatures(tc.temperatures)
		fmt.Printf("Test Case %d, Input: temperatures = %v\n", i+1, tc.temperatures)

		if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}