该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

每日温度

题目背景

本题是单调栈数据结构的经典应用，属于"下一个更大元素"系列问题。通过维护一个单调递减的栈，可以在一次遍历中高效求解所有位置的下一个更大元素，时间复杂度达到线性级别，是处理此类区间查询问题的最优方法。

题目描述

给定一个整数数组 $temperatures$，表示连续 $n$ 天的每日温度。请你计算并输出一个长度为 $n$ 的数组 $answer$，其中 $answer[i]$ 表示：对于第 $i$ 天，下一个温度比当天更高的天数。如果在这之后再也没有温度升高的情况，则在该位置填入 $0$。

输入格式

第一行一个正整数 $n$，表示总天数。

第二行 $n$ 个整数 $t_1, t_2, \dots, t_n$，依次表示第 $1$ 天到第 $n$ 天的温度。

输出格式

一行 $n$ 个整数，依次表示 $answer[1], answer[2], \dots, answer[n]$，整数之间用一个空格分隔。

样例 #1

样例输入 #1

8
73 74 75 71 69 72 76 73

样例输出 #1

1 1 4 2 1 1 0 0

样例解释 #1

• 第1天温度73，下一个更高温度在第2天（74），间隔1天
• 第3天温度75，下一个更高温度在第7天（76），间隔4天
• 第7、8天之后没有更高温度，因此答案为0

样例 #2

样例输入 #2

4
30 40 50 60

样例输出 #2

1 1 1 0

样例 #3

样例输入 #3

3
30 60 90

样例输出 #3

1 1 0

提示

数据范围与约定

• 对于 $100\%$ 的数据，保证：
  • $1 \le n \le 10^5$
  • $30 \le temperatures[i] \le 100$

算法提示

1. 暴力枚举法：对于每个位置 $i$，向后遍历找到第一个比 $t[i]$ 大的元素，计算间隔天数。时间复杂度 $O(n^2)$，对于 $n=10^5$ 会严重超时，无法通过全部测试点。
2. 单调栈解法（推荐）：
   • 维护一个单调递减栈，栈中存储温度对应的下标，保证栈中下标对应的温度从栈底到栈顶单调递减。
   • 遍历数组时，对于当前温度 $t[i]$：
     • 若栈不为空且 $t[i] > t[栈顶下标]$，说明找到了栈顶元素的下一个更高温度，弹出栈顶元素并计算间隔天数 $i - 栈顶下标$，存入答案数组。
     • 重复上述过程，直到栈为空或 $t[i] \le t[栈顶下标]$，将当前下标 $i$ 压入栈中。
   • 遍历结束后，栈中剩余元素对应的位置没有下一个更高温度，答案保持为 $0$。
   • 时间复杂度 $O(n)$，每个元素最多入栈和出栈一次；空间复杂度 $O(n)$，最坏情况下栈的大小为 $n$。