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代表没有更高的温度）。

---

队列与双端队列对照（原 others 笔记）

Queues 队列

队列是一种先进先出 First In First Out（FIFO）的数据结构，支持三种操作，所有操作的时间复杂度均为 $\mathcal{O}(1)$ 。

std::queue

• push: 在队列的末尾插入

• pop: 从队列的前端删除

• front: 获取前端元素但不将其移除

queue<int> q;
q.push(1);                  // [1]
q.push(3);                  // [1, 3]
q.push(4);                  // [1, 3, 4]
q.pop();                    // [3, 4]
cout << q.front() << endl;  // 3

from queue import Queue

q = Queue()           # []
q.put(1)              # [1]
q.put(2)              # [1, 2]
v = q.queue[0]        # v = 1, q = [1, 2]
v = q.get()           # v = 1, q = [2]
v = q.get()           # v = 2, q = []
v = q.get()           # 代码会一直等待，导致TLE错误

Deques 双端队列

一个双端队列（通常发音为“deck”）代表双端队列，它是栈和队列的结合，支持在双端队列的前后两端进行插入和删除操作。

std::deque

添加和删除的四种方法是 push_back , pop_back , push_front , 和 pop_front 。

deque<int> d;

d.push_front(3);  // [3]
d.push_front(4);  // [4, 3]
d.push_back(7);   // [4, 3, 7]
d.pop_front();    // [3, 7]
d.push_front(1);  // [1, 3, 7]
d.pop_back();     // [1, 3]

d = collections.deque()
d.appendleft(3)  # [3]
d.appendleft(4)  # [4, 3]
d.append(7)  # [4, 3, 7]
d.popleft()  # [3, 7]
d.appendleft(1)  # [1, 3, 7]
d.pop()  # [1, 3]

你也可以像用数组的 [] 运算符一样，以常数时间访问双端队列中的元素。例如，要访问双端队列 $\texttt{dq}$ 中的 $i$ 个元素，可以使用 $\texttt{dq}[i]$ 。