单调栈

单调栈是一种特殊的栈数据结构，具有以下特点：

单调递增栈：栈内的元素从栈底到栈顶严格递增（或者非递减）。
单调递减栈：栈内的元素从栈底到栈顶严格递减（或者非递增）。

那有同学就问了，我怎么能想到用单调栈呢？ 什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

问题解析：每日温度

我们给定一个数组 temperatures，表示每天的气温，我们需要找到每个元素的下一个更高气温所对应的天数，也就是找到当前温度之后，直到遇到更高的温度所需的天数。如果没有更高的温度，返回 0。

输入：
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

输出：
[1, 1, 4, 2, 1, 1, 0, 0]

---

单调栈解法：

1. 目标： 我们希望对每个元素 temperatures[i] 找到其右边第一个比它大的元素，并记录从当前位置到这个元素的天数。
2. 核心思路：
   • 遍历数组时，我们用一个栈来存储当前未找到下一个更高气温的索引。
   • 如果当前气温大于栈顶对应的气温，说明栈顶的元素找到了“下一个更高气温”，我们可以计算天数并将栈顶弹出。
   • 如果当前气温不大于栈顶气温，我们将当前元素的索引入栈，等待以后元素来为栈中的元素找到答案。

---

具体步骤：

1. 初始化：
   • 创建一个空栈 stack 用于存储未找到下一个更大气温的元素的索引。
   • 创建一个与 temperatures 同样大小的数组 res 来保存每个元素的结果，初始值为 0（如果没有更高的气温，结果为 0）。
2. 遍历过程：
   • 对每个气温进行遍历。
   • 比较当前气温与栈顶元素的气温：
     • 如果当前气温较高，说明栈顶元素的“下一个更高气温”已经找到了，更新结果并弹出栈顶。
     • 如果当前气温不高，将当前元素的索引入栈，继续遍历。
3. 结束后：
   • 栈中剩下的元素没有更高气温，默认结果为 0。