739. 每日温度

link

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

思路

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

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。
更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

核心点：

单调栈里存放的元素是什么？
单调栈里只需要存放元素的下标 i 就可以了，如果需要使用对应的元素，直接 T[i] 就可以获取。
单调栈里元素是递增呢？还是递减呢？
顺序的描述为从栈头到栈底的顺序，这里要使用递增循序，因为只有递增的时候，栈里要加入一个元素 i 的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是 i。

单调栈满足：

栈中存的是“还没找到更高温度的那些天”，即：这些天还在等更暖的一天。当发现某天比他们“暖”，就将他们移出栈，并更新它们的等待时间。
栈保持的是“温度单调递减”，因为只有温度递减才会出现“等待更暖的天”。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []

        res = [0] * len(temperatures)

        for i in range(0, len(temperatures)):
            while len(stack) > 0:
                if temperatures[stack[-1]] < temperatures[i]:
                    res[stack[-1]] = i - stack[-1]
                    stack.pop()
                else:
                    break
            
            stack.append(i)
        return res

以上代码为精简版，即如果栈不为空，就一直比较：

如果当前元素比栈底元素大，说明找到了第一个大于当前元素的元素，就可以更新结果。为了保证栈的递增性，就要把当前元素移出，然后再循环判断
如果当前元素比栈底元素小，说明当前元素不满足要求，跳出循环
最后在 while 循环外将当前元素添加到栈中（无论如何都需要添加）

496.下一个更大元素 I

link

给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

思路

类似于上一题，首先针对 nums2 中的每一个元素，在其右边找到第一个大于当前元素的元素存放在 res 中，如果找不到就存 -1（默认值为 -1）。然后对于 nums1 中的每一个元素，先在 nums2 中找到下标，然后将 res 中对应下标的值存到新的 res 中。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = [-1] * len(nums2)
        stack = []
        for i in range(len(nums2)):
            while len(stack) > 0:
                if nums2[stack[-1]] < nums2[i]:
                    res[stack[-1]] = nums2[i]
                    stack.pop()
                else:
                    break
                
            stack.append(i)
        
        new_res = []
        # 也可以使用哈希表来存储
        for i in nums1:
            cur = res[nums2.index(i)]
            new_res.append(cur)
        return new_res

503. 下一个更大元素 II

link

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

思路

要处理循环数组，可以遍历当前数组两次来模拟（相当于是把两个相同的数组拼在一起）。每次处理下标是，都需要取余操作。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        stack = []
        n = len(nums)
        res = [-1] * n
        for i in range(n * 2):
            while len(stack) > 0:
                cur = stack[-1]
                if nums[cur % n] < nums[i % n]:
                    res[cur % n] = nums[i % n]
                    stack.pop()
                else:
                    break
            
            stack.append(i)
        
        return res

42. 接雨水

link

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

思路 1

核心点：每一根柱子上方能接多少水，取决于：它左边最高的柱子 和 右边最高的柱子 的较小值，减去自己的高度，即 water[i] = min(max_left[i], max_right[i]) - height[i]

所以先正向和反向都遍历一遍，找到当前柱子左右两边的最大值，然后通过上述公式计算即可。

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        
        max_left = [0] * n
        max_right = [0] * n

        # 从左向右预处理左侧最大高度
        max_left[0] = height[0]
        for i in range(1, n):
            max_left[i] = max(max_left[i - 1], height[i])

        # 从右向左预处理右侧最大高度
        max_right[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            max_right[i] = max(max_right[i + 1], height[i])

        # 计算每个柱子上方可接雨水量
        total_water = 0
        for i in range(n):
            water = min(max_left[i], max_right[i]) - height[i]
            if water > 0:
                total_water += water

        return total_water

这种方法是按列来进行计算的。

思路 2

使用一个单调递减栈（存的是下标）来找出：

当前柱子是否可以构成一个“接水凹槽”
如果可以，我们就计算凹槽中间那一段的接水量

每次遇到更高的柱子，就回头找左边有没有柱子能形成一对“墙”。

假设当前遍历到下标 i，高度为 height[i]：

如果栈为空或当前高度 <= 栈顶高度：
- 入栈（表示还没形成接水凹槽）。
如果当前高度 > 栈顶高度：
- 说明可能形成“接水凹槽”，开始出栈并计算。
每次出栈后：
- 栈顶是凹槽的左墙
- 当前是右墙
- 被出栈的那个柱子是底部
水的计算方式：
- 高度 = min(左墙高度, 右墙高度) - 底部高度
- 宽度 = 右墙索引 - 左墙索引 - 1
- 水量 = 高度 × 宽度

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        water = 0

        for i in range(len(height)):
            
            while stack:
                if height[stack[-1]] < height[i]:
                    last = stack.pop()
                    # 注意底部出栈后，可能没有左墙，则需要跳出当前循环
                    if not stack:
                        break
                    
                    w = i - stack[-1] - 1
                    # last 是底部，i 是右墙，stack[-1] 是左墙
                    h = min(height[stack[-1]], height[i]) - height[last]

                    water += h * w
                else:
                    break
            stack.append(i)
        
        return water

这种方法是按行来计算的：

84.柱状图中最大的矩形

link

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1：

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

思路 1

目标：找出每个柱子向左和向右能延伸的最大范围，即为当前柱子能构成的最大矩形。使用单调栈，只不过从栈头到栈尾是递增的。

当前柱子高度比栈顶高 → 继续入栈（栈保持递增）
当前柱子高度比栈顶低 → 出栈，并计算以该柱子（出栈的那个柱子）为高的最大矩形
- 矩形的高：当前出栈的柱子
- 矩形宽的起点：出栈之后的栈顶
- 矩形宽的终点：当前 i
- 注意，如果出栈的柱子下标和当前 i 不相邻，则说明之前一定有一个（或多个）更高的柱子出栈过，此时就是跨柱子框选矩形的情况了。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        size = 0
        heights = [0] + heights + [0]
        stack = []

        for i in range(len(heights)):
            while stack:
                if heights[stack[-1]] > heights[i]:
                    last = stack.pop()
                    w = i - stack[-1] - 1
                    h = heights[last]
                    cur = h * w
                    size = max(cur, size)
                else:
                    break
            
            stack.append(i)

        return size

注意，这里需要在 heights 的左右各添加一个哨兵 0，用于处理边界的情况。对比接雨水和本题：

柱状图最大矩形 需要哨兵：
- 本质：每根柱子都可能是最大矩形的“最矮墙”
- 所以每根柱子都要参与处理
- 但单调栈不会主动处理栈中剩下的元素，必须手动“清栈”
- 加个尾部哨兵 0 会自动触发清栈逻辑，不需要额外代码
接雨水 不需要哨兵：
- 本质：只在当前柱子比栈顶高时才处理接水逻辑
- 不满足条件（右墙不高）就跳过
- 到最后一根柱子后，也不需要强制处理栈里剩下的柱子
- 因为没有右墙就不会装水

思路 2

同样，本题也可以类似于接雨水，对每个柱子，找到左右两边第一个小于当前柱子的柱子。然后构建的矩形的高为当前柱子，，宽度是能延伸到左右两边第一个比它小的柱子之间的范围。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left = [-1] * n      # 左边第一个比它小的位置
        right = [n] * n      # 右边第一个比它小的位置
        stack = []

        # 计算 left[]
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            left[i] = stack[-1] if stack else -1
            stack.append(i)

        stack.clear()

        # 计算 right[]
        for i in reversed(range(n)):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            right[i] = stack[-1] if stack else n
            stack.append(i)

        # 枚举每个柱子作为矩形的“最矮边”
        max_area = 0
        for i in range(n):
            width = right[i] - left[i] - 1
            area = heights[i] * width
            max_area = max(max_area, area)

        return max_area