LeetCode739每日温度：如何判断选用单调递增/递减栈？

单调栈的核心作用是用O(n)的线性时间，快速找到每个元素左侧/右侧第一个满足大小关系的元素，到底选单调递增还是递减栈，完全由你要找的目标和当前元素的大小关系决定，规则非常明确，不用死记硬背各种题目场景：

• 要找第一个比当前元素大的元素（比如这道题找下一个更暖的天，也就是右侧第一个气温更高的日子），用单调递减栈——也就是栈底到栈顶存的索引对应的气温值是从大到小排的。
  原理很简单：维护栈递减特性的时候，只要当前遍历到的气温大于等于栈顶索引对应的气温，栈顶这个索引对应的日子，就不可能成为它前面任何一天要找的「第一个更暖的天」，直接弹掉就行。等所有不符合的元素都弹完，剩下的栈顶就是离当前天最近的、气温更高的日子，直接算天数差就行。
• 要找第一个比当前元素小的元素（比如你说的改完题目找下一个更冷的天，也就是右侧第一个气温更低的日子），用单调递增栈——也就是栈底到栈顶存的索引对应的气温值是从小到大排的。
  逻辑和上面完全对称：维护栈递增特性的时候，只要当前遍历到的气温小于等于栈顶索引对应的气温，栈顶这个索引就不可能成为前面任何一天要找的「第一个更冷的天」，直接弹掉。弹完剩下的栈顶就是最近的气温更低的日子。

注意：这里说的递增/递减，说的是栈里存的索引对应的数值大小顺序，和索引本身的先后没关系；遍历是正序还是倒序，只影响你找的是当前元素左边还是右边的目标，不影响栈的单调性选择——不管从哪头开始遍历，找更大值就用递减栈，找更小值就用递增栈。

对你的猜想的答复 #

你的猜想完全正确。如果题目改成找下一个更冷的气温，只要把原代码里维护栈的判断条件反过来，用单调递增栈就能实现，核心代码参考：

def dailyColderTemperatures(self, temperatures: List[int]) -> List[int]:
    mono_increasing_stack = []
    N = len(temperatures)
    res = [0] * N
    for i in reversed(range(0, N)):
        temp = temperatures[i]
        # 维护单调递增栈，弹出所有气温大于等于当前值的栈顶元素
        while mono_increasing_stack and temp <= temperatures[mono_increasing_stack[-1]]:
            mono_increasing_stack.pop()
        if mono_increasing_stack:
            res[i] = mono_increasing_stack[-1] - i
        mono_increasing_stack.append(i)
    return res

你之前写的每日温度的倒序遍历+单调递减栈解法是标准最优解，时间复杂度符合要求。
给你列几个常见场景对应栈类型，方便你后续快速判断：

• 单调递减栈（找更大值）：下一个更大元素系列题、接雨水、每日温度
• 单调递增栈（找更小值）：下一个更小元素系列题、柱状图中最大矩形、求字典序最小子序列

内容的提问来源于stack exchange，提问作者Victor Cui