一个不肯留下无用元素的栈，一趟扫描就能回答整个数组里每个元素的“下一个更大元素”是谁。同样的结构还能求出柱状图中最大的矩形。
栈是每个人最先学的数据结构，却也是大家最想不到去用的那一个。这一篇的关键不在栈本身，而在于决定哪些东西不许留在栈里。
下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里粘贴过来。
模式 21 — 单调栈
对每个元素，找出它右边第一个比它大的元素。
拿每个元素去和它后面的所有元素比，是 O(n²)。线性解法来自一个观察：从左往右扫的时候，总有一些元素还在等答案。只留下这些元素，别的一概不要。
新值到来时，它会给所有比它小的等待者一个答案，可能一次好几个，然后自己也排进等待队伍。每个等待者只会被第一个比它大的值解决，所以等待列表从栈底到栈顶始终是递减的。这里的“单调”就是这个意思。
栈里存的是还在等答案的索引，它们对应的值从栈底到栈顶始终递减。新值比栈顶高，就解决栈顶 — 可能连同下面好几个一起，都在同一步里完成。
int[] a = [2, 1, 2, 4, 3];
int[] answer = new int[a.Length];
Array.Fill(answer, -1);
Stack<int> st = []; // indices, values DECREASING from bottom to top
for (int i = 0; i < a.Length; i++)
{
while (st.Count > 0 && a[st.Peek()] < a[i])
{
int j = st.Pop();
answer[j] = a[i];
Console.WriteLine($"i={i} a[i]={a[i]} resolves index {j} (value {a[j]}) -> next greater is {a[i]}");
}
st.Push(i);
Console.WriteLine($"i={i} a[i]={a[i]} push stack(values)=[{string.Join(",", st.Select(k => a[k]).Reverse())}]");
}
Console.WriteLine($"\nleft unresolved: [{string.Join(", ", st.Select(k => $"a[{k}]={a[k]}").Reverse())}] -> no greater element exists");
Console.WriteLine($"a = [{string.Join(", ", a)}]");
Console.WriteLine($"answer = [{string.Join(", ", answer)}]");输出：
i=0 a[i]=2 push stack(values)=[2]
i=1 a[i]=1 push stack(values)=[2,1]
i=2 a[i]=2 resolves index 1 (value 1) -> next greater is 2
i=2 a[i]=2 push stack(values)=[2,2]
i=3 a[i]=4 resolves index 2 (value 2) -> next greater is 4
i=3 a[i]=4 resolves index 0 (value 2) -> next greater is 4
i=3 a[i]=4 push stack(values)=[4]
i=4 a[i]=3 push stack(values)=[4,3]
left unresolved: [a[3]=4, a[4]=3] -> no greater element exists
a = [2, 1, 2, 4, 3]
answer = [4, 2, 4, -1, -1]看 i=3 这一步。值 4 一次解决了两个等待中的元素，而且哪个都不用再回头看。扫描结束时还留在栈里的两个元素没有得到答案，这完全正确：它们右边根本没有更大的值。
嵌套的 while 看起来像平方级。其实不是：每个索引恰好入栈一次，最多出栈一次，所以整趟扫描的总工作量不超过 2n。
代价： O(n) 时间，O(n) 空间。
适用场景： 问题是下一个更大元素、上一个更小元素、还要多远才遇到更高的、股票价格跨度、每日温度。把比较方向反过来，就得到“更小”的版本。
模式 22 — 柱状图中最大的矩形
这是上面那个模式真正派上用场的地方。
以柱子 i 的完整高度做矩形，往右延伸到遇见一根更矮的柱子为止，往左也是一样。所以它的宽度由两侧各自的下一个更小元素决定，也就是把模式 21 跑两遍。
单调栈一趟就能给出两侧边界。某根柱子出栈时，正在到来的那个值就是它的右边界，出栈后栈里它下面的那个元素就是它的左边界。
每个矩形都受限于两侧第一根更矮的柱子 — 也就是把“下一个更小元素”问两次。所以单调栈能解这道题：一根柱子出栈，两侧边界就同时知道了。
int[] h = [2, 1, 5, 6, 2, 3];
// The sentinel: a zero-height bar past the end forces every remaining bar to
// be resolved, so there is no separate drain loop after the scan.
int[] bars = [.. h, 0];
Stack<int> st = [];
int best = 0;
for (int i = 0; i < bars.Length; i++)
{
while (st.Count > 0 && bars[st.Peek()] >= bars[i])
{
int top = st.Pop();
int height = bars[top];
int left = st.Count == 0 ? -1 : st.Peek();
int width = i - left - 1;
int area = height * width;
Console.WriteLine($"i={i} pop bar {top} (height {height}) spans ({left}..{i}) exclusive width {width} area {area}");
best = Math.Max(best, area);
}
st.Push(i);
}
Console.WriteLine($"\nlargest rectangle: {best}");输出：
i=1 pop bar 0 (height 2) spans (-1..1) exclusive width 1 area 2
i=4 pop bar 3 (height 6) spans (2..4) exclusive width 1 area 6
i=4 pop bar 2 (height 5) spans (1..4) exclusive width 2 area 10
i=6 pop bar 5 (height 3) spans (4..6) exclusive width 1 area 3
i=6 pop bar 4 (height 2) spans (1..6) exclusive width 4 area 8
i=6 pop bar 1 (height 1) spans (-1..6) exclusive width 6 area 6
largest rectangle: 10有两个细节缺一不可。
哨兵。 数组末尾追加了一根高度为 0 的柱子。没有它，扫描结束时还留在栈里的柱子就得另写一个清空循环，逻辑还略有不同，而 bug 恰恰藏在这段重复的逻辑里。高度为 0 的柱子比谁都矮，主循环因此会把剩下的柱子全部处理掉。
宽度。 宽度是 i - left - 1，其中 left 是栈里出栈柱子下面那个索引，不是出栈的柱子本身。两侧边界都是开区间：跨度严格位于两根更矮的柱子之间。这里差一，得到的答案在小输入上看起来还挺像回事。
代价： O(n) 时间，O(n) 空间。
适用场景： 求最大的矩形、二值矩阵中最大的正方形（每行跑一次这个算法），或者任何“能延伸多宽才被挡住”的问题。
模式 23 — 括号匹配
栈最朴素的用法。值得收进来，是因为出错的地方都在细节里。
static bool Valid(string s)
{
Dictionary<char, char> pairs = new() { [')'] = '(', [']'] = '[', ['}'] = '{' };
Stack<char> st = [];
foreach (char c in s)
{
if (pairs.ContainsValue(c)) { st.Push(c); continue; }
if (!pairs.TryGetValue(c, out char open)) continue; // not a bracket
if (st.Count == 0 || st.Pop() != open) return false;
}
return st.Count == 0;
}
foreach (string s in new[] { "{[()]}", "([)]", "(((", "", "a(b[c]d)e" })
Console.WriteLine($"{$"\"{s}\"",12} -> {Valid(s)}");输出：
"{[()]}" -> True
"([)]" -> False
"(((" -> False
"" -> True
"a(b[c]d)e" -> True大家容易忘的两种情况都在这份输出里。"(((" 不合法，不是因为发现了不匹配，而是因为最后栈不为空：每个左括号都需要配对。"" 合法，这也是同一个检查自然得出的结果，不需要特判。
"([)]" 正是非用栈不可的原因。给每种括号各设一个计数器，会判它合法：一个 (、一个 )、一个 [、一个 ]。嵌套讲的是顺序，而只有栈会记录顺序。
代价： O(n) 时间，O(n) 空间。
适用场景： 任何有嵌套的东西：括号、标签、表达式解析、撤销历史。
模式 24 — 知道自己最小值的栈
在不断入栈、出栈的同时，用 O(1) 报告栈里所有元素的最小值。
只维护一个 min 变量，出栈时就会出问题：最小值被弹出后，得重新找次小值，那是 O(n)。
解决办法是别再把最小值当成整个栈的一个事实。给每个元素都存一份“它自己及其下方所有元素的最小值”。
每个元素多存一个 int，换来 O(1) 的 Min()。出栈后依然正确，是因为每个条目的最小值只由它下面的元素算出，从不依赖后来的元素。
// Each entry carries the minimum of everything at or below it. That makes Min
// a peek, and costs one extra int per element.
Stack<(int value, int min)> st = [];
void Push(int v)
{
int min = st.Count == 0 ? v : Math.Min(v, st.Peek().min);
st.Push((v, min));
Console.WriteLine($"push {v,3} min is now {min,3} stack=[{string.Join(" ", st.Select(x => $"{x.value}/{x.min}").Reverse())}]");
}
foreach (int v in new[] { 5, 2, 7, 2, 9 }) Push(v);
Console.WriteLine();
while (st.Count > 0)
{
var (v, m) = st.Peek();
Console.WriteLine($"top {v,3} Min() = {m,3}");
st.Pop();
}输出：
push 5 min is now 5 stack=[5/5]
push 2 min is now 2 stack=[5/5 2/2]
push 7 min is now 2 stack=[5/5 2/2 7/2]
push 2 min is now 2 stack=[5/5 2/2 7/2 2/2]
push 9 min is now 2 stack=[5/5 2/2 7/2 2/2 9/2]
top 9 Min() = 2
top 2 Min() = 2
top 7 Min() = 2
top 2 Min() = 2
top 5 Min() = 5出栈完全不需要重新计算，原因值得说清楚：每个条目的最小值只由它下面的元素算出，从不依赖后来的元素。移除后来的条目，不会让它失效。
代价是每个元素多一个 int。看输出里的出栈序列：上面的元素全部弹出后，5 正确地报告自己的最小值是 5。
代价： 入栈、出栈、取最小值都是 O(1)。O(n) 空间。
适用场景： 需要一个在出栈后依然成立的累计量。同样的结构也适用于最大值，或者 gcd。
模式 25 — C# 没有自带的容器
Stack<T> 和 Queue<T> 都有，也都好用。但没有基于数组的双端队列，没有 ArrayDeque。
LinkedList<T> 能胜任，第 2 篇的滑动窗口最大值用的就是它。但它给每个元素都分配一个节点对象，在竞赛级别的输入规模下，这些分配会体现在耗时上。基于单个数组的环形缓冲区没有这个开销，而且代码短到可以凭记忆敲出来。
C# 自带 Stack<T> 和 Queue<T>，却没有基于数组的双端队列。LinkedList<T> 可以补上，但每个元素分配一个节点对象；环形缓冲区只分配一个数组，大约三十行代码。
var d = new Deque(8);
d.PushBack(1); d.PushBack(2); d.PushBack(3);
Console.WriteLine($"pushed 1,2,3 at the back {d}");
d.PushFront(0);
Console.WriteLine($"pushed 0 at the front {d} (head wrapped round to the end of the array)");
Console.WriteLine($"first={d.First} last={d.Last}");
Console.WriteLine($"popFront -> {d.PopFront()} {d}");
Console.WriteLine($"popBack -> {d.PopBack()} {d}");
// A full array has to grow. Without the check the next push lands on the head.
var small = new Deque(2);
small.PushBack(1); small.PushBack(2);
Console.WriteLine($"\nsmall deque, now full {small} count={small.Count} capacity={small.Capacity}");
small.PushBack(3);
Console.WriteLine($"pushed 3 into a full array {small} count={small.Count} capacity={small.Capacity} nothing lost");
// Empty is an error, not a stale cell.
try { _ = new Deque(4).First; }
catch (InvalidOperationException ex) { Console.WriteLine($"First on an empty deque -> {ex.Message}"); }
Console.WriteLine();
Stack<int> st = []; st.Push(1); st.Push(2);
Queue<int> q = []; q.Enqueue(1); q.Enqueue(2);
Console.WriteLine($"Stack<int> Peek={st.Peek()} LIFO — Push / Pop / Peek");
Console.WriteLine($"Queue<int> Peek={q.Peek()} FIFO — Enqueue / Dequeue / Peek");
Console.WriteLine($"Deque {d} both ends, one array, no per-item allocation");
// In a file-based app, type declarations come AFTER the top-level statements.
class Deque(int cap)
{
int[] buf = new int[Math.Max(1, cap)];
int head = 0, count = 0;
public int Count => count;
public int Capacity => buf.Length;
public int First => count > 0 ? buf[head] : throw new InvalidOperationException("deque is empty");
public int Last => count > 0 ? buf[(head + count - 1) % buf.Length] : throw new InvalidOperationException("deque is empty");
public void PushBack(int v) { if (count == buf.Length) Grow(); buf[(head + count) % buf.Length] = v; count++; }
public void PushFront(int v) { if (count == buf.Length) Grow(); head = (head - 1 + buf.Length) % buf.Length; buf[head] = v; count++; }
public int PopFront() { int v = First; head = (head + 1) % buf.Length; count--; return v; }
public int PopBack() { int v = Last; count--; return v; }
void Grow()
{
var bigger = new int[buf.Length * 2];
for (int i = 0; i < count; i++) bigger[i] = buf[(head + i) % buf.Length];
buf = bigger;
head = 0;
}
public override string ToString()
{
var parts = new List<int>();
for (int i = 0; i < count; i++) parts.Add(buf[(head + i) % buf.Length]);
return "[" + string.Join(", ", parts) + "]";
}
}输出：
pushed 1,2,3 at the back [1, 2, 3]
pushed 0 at the front [0, 1, 2, 3] (head wrapped round to the end of the array)
first=0 last=3
popFront -> 0 [1, 2, 3]
popBack -> 3 [1, 2]
small deque, now full [1, 2] count=2 capacity=2
pushed 3 into a full array [1, 2, 3] count=3 capacity=4 nothing lost
First on an empty deque -> deque is empty
Stack<int> Peek=2 LIFO — Push / Pop / Peek
Queue<int> Peek=1 FIFO — Enqueue / Dequeue / Peek
Deque [1, 2] both ends, one array, no per-item allocation核心就是 % buf.Length。在前端入队时，head 往回退，退过头就绕到数组末尾；没有移动任何元素，只是元素不再按逻辑顺序存放。ToString 按 head, head+1, … 对长度取模依次访问，把逻辑顺序还原出来。
注意 PushFront 里的 + buf.Length。在 C# 里，-1 % 8 是 -1，不是 7：% 运算符的结果和左操作数同号。漏掉这一项会得到负索引，而它抛出的异常离真正出错的那一行很远。
剩下的分量压在两道检查上。没有它们的环形缓冲区算不上数据结构，只是个陷阱。
往满数组里入队，必须先扩容。 没有 count == buf.Length 这个检查，(head + count) % buf.Length 会绕回 head 自己的格子并写进去。什么异常都不抛。上面那个两格的双端队列装着 [1, 2]，再入队一次，读出来就成了 [3, 2, 3]，count 是 3：1 没了，3 被算了两次，容量悄无声息地超了。Grow() 按逻辑顺序把元素复制到一个两倍大的数组里，并把 head 重置为 0，这是环唯一可以“拉直”自己的时刻。
空队列是错误，不是一个值。 First 和 Last 读取之前先检查 count > 0。没有这个检查，对空队列取 First 会返回 buf[head] 里残留的东西：一个你早已弹出的值，却被当成有效值返回。这比崩溃更糟，因为程序会继续跑下去。Last 出错的方式不同，但同样帮不上忙：head 和 count 都是 0 时，它计算 (0 + 0 - 1) % 8，结果是 -1，然后从一行看起来和错误毫不相干的代码里抛出 IndexOutOfRangeException。
代价： 两端都是 O(1)，扩容时均摊 O(1)，任何时候只占一个数组。
适用场景： 需要同时操作两端：滑动窗口最大值、第 8 篇的 0-1 BFS，或者任何有零权边的 BFS。
要点
- 单调栈只保存还在等答案的元素。 它们之所以有序，是因为每个元素都由第一个比它大的值来解决。
- 嵌套的
while依然是线性的。 每个索引进一次、出一次。心里要把这句话过一遍，别只看代码的形状下结论。 - 用哨兵代替清空循环。 末尾加一根高度为 0 的柱子，主循环就会处理完所有元素，也省掉了容易藏 bug 的重复逻辑。
- 柱状图的宽度两侧都是开区间。
i - left - 1，其中left取自出栈之后的栈顶。 - 没闭合的括号，就是最后栈不为空。 靠这一个检查，
"((("判为不合法，""判为合法，不需要任何特判。 - 最小栈给每个元素都存最小值，而不是只存一份。 它出栈后依然正确，因为它只往下看过。
- C# 没有基于数组的双端队列，而且
-1 % 8是-1。 每次取模前都先加上长度。
第 6 篇讲真正的容器：字典、自定义比较器、坐标压缩，以及 PriorityQueue<TElement, TPriority>。它直到 .NET 6 才出现，很多老的 C# 竞赛资料至今还在绕开它。