04_队列与栈

队列

from collections import deque

dq = deque()
dq.append(x)
dq.appendleft(x)
dq.pop()
dq.popleft()

单调队列

from collections import deque

# 求窗口最小值（递增队列）
q = deque()
for i in range(n):
    while q and q[0][0] < i - k:      # 超出窗口
        q.popleft()
    while q and q[-1][1] >= arr[i]:   # 队尾不优
        q.pop()
    q.append((i, arr[i]))
    min_val = q[0][1]

# 求窗口最大值（递减队列）
q = deque()
for i in range(n):
    while q and q[0][0] < i - k:
        q.popleft()
    while q and q[-1][1] <= arr[i]:
        q.pop()
    q.append((i, arr[i]))
    max_val = q[0][1]

单调栈

单调栈就是一个普通的栈，栈里的元素（通常是索引，或者元素值）从栈底到栈顶保持单调递增或递减。

• 单调递增栈：栈底最小，栈顶最大。新元素入栈时，如果它比栈顶小，就弹出栈顶，直到能保持递增。

• 单调递减栈：栈底最大，栈顶最小。新元素入栈时，如果它比栈顶大，就弹出栈顶，直到能保持递减。

核心作用：
当你在遍历数组时，利用单调栈可以在 O(n) 时间内找到每个元素左边或右边第一个比它大（或小）的元素。
因为弹出元素时，当前遍历到的元素就是被弹出元素的“右边第一个更大/更小元素”。

---

下一个更大元素模板详解

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n           # 保存答案，默认-1表示没有更大元素
    stack = []                  # 栈里存索引，栈底到栈顶对应的值单调递减
    for i in range(n):
        # 当前元素 > 栈顶索引所对应的元素 → 说明当前元素是栈顶的“下一个更大元素”
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()   # 弹出栈顶索引
            result[idx] = nums[i]   # 记录答案
        stack.append(i)         # 当前索引入栈
    return result

举例说明

假设 nums = [2, 1, 3, 4]

• i=0 (值2)：栈空，直接入栈 → stack=[0]

• i=1 (值1)：while条件：stack不为空，nums[1]=1 > nums[0]=2？错，不弹出。入栈 → stack=[0,1]（对应值[2,1] 单调递减 ✅）

• i=2 (值3)：while条件：nums[2]=3 > nums[1]=1？成立 → 弹出1，result[1]=3（索引1的右边第一个更大是3）。栈变[0]，继续while：3 > nums[0]=2？成立 → 弹出0，result[0]=3。栈空。循环结束。入栈i=2 → stack=[2]（值[3]）

• i=3 (值4)：while：4 > nums[2]=3 → 弹出2，result[2]=4。入栈3 → stack=[3]

最终 result=[3,3,4,-1] 即每个索引右边第一个更大元素。

关键理解：

• 栈中存放的索引，它们对应的值是从栈底到栈顶单调递减的（即越往栈顶越小）。

• 遇到一个新元素，如果它比栈顶索引对应的值大，那么它就是栈顶元素的“下一个更大元素”，所以弹出并记录答案。

• 弹出后，新栈顶仍然比当前元素小吗？继续比较，直到栈为空或栈顶值更大。

• 最后把当前索引入栈，保持单调递减。

---

每日温度 LC 739 解释

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev = stack.pop()
            answer[prev] = i - prev   # 天数差 = 当前索引 - 之前索引
        stack.append(i)
    return answer

与下一个更大元素的区别

• 下一个更大元素：答案存的是那个元素的值。

• 每日温度：答案存的是距离（索引差）。
  但原理完全一样：找到右边第一个温度更高的天数，用 i - prev 得到需要等待的天数。

举例

temps = [73, 74, 75, 71, 69, 72, 76, 73]

• i=0 (73)：栈空，入栈 [0]

• i=1 (74)：74 > 73 → 弹出0，answer[0]=1-0=1。入栈1 → [1]

• i=2 (75)：75 > 74 → 弹出1，answer[1]=1。入栈2 → [2]

• i=3 (71)：71 > 75？否，不入栈 → [2,3]

• i=4 (69)：69 > 71？否，入栈 → [2,3,4]

• i=5 (72)：72 > 69 → 弹出4，answer[4]=5-4=1；继续 72 > 71 → 弹出3，answer[3]=5-3=2；继续 72 > 75？否。入栈5 → [2,5]

• i=6 (76)：76 > 72 → 弹出5，answer[5]=1；76 > 75 → 弹出2，answer[2]=4；入栈6 → [6]

• i=7 (73)：73 > 76？否，入栈 → [6,7]

结果 answer = [1,1,4,2,1,1,0,0]，表示需要等待的天数（0代表没有更高的温度）。