算法编程题：栈、队列与单调结构（7 题）
032 判断只含括号字符的字符串是否有效。
难度： 基础
方法签名： string text
输入约束： text 仅包含 ()[]{}
示例： ”{[()]}” → true
目标复杂度： 时间 O(n)，额外空间 O(n)
查看参考答案
解题思路： 左括号入栈，右括号必须匹配最近的未闭合左括号。
不变量： 栈从底到顶保存所有尚未匹配的左括号。
public static class AlgCode032Solution
{
public static bool Solve(string text)
{
var stack = new Stack<char>();
foreach (char value in text)
{
if (value is '(' or '[' or '{')
{
stack.Push(value);
continue;
}
if (stack.Count == 0) return false;
char open = stack.Pop();
if ((value == ')' && open != '(') ||
(value == ']' && open != '[') ||
(value == '}' && open != '{'))
return false;
}
return stack.Count == 0;
}
}复杂度： 时间 O(n)，额外空间 O(n)。
边界用例： 空字符串；右括号开头；结束时仍有左括号。
面试追问：
- 如果括号种类由配置提供，如何避免硬编码分支？
033 实现所有操作均为 O(1) 的最小栈。
难度： 进阶
方法签名： MinStack Create()
输入约束： 调用 Pop、Top、GetMin 前栈非空
示例： Push(3), Push(1), GetMin() → 1
目标复杂度： Push、Pop、Top、GetMin 均为 O(1)
查看参考答案
解题思路： 每次压入值时同步保存截至当前的最小值。
不变量： 每个栈项都记录该位置及其以下元素的最小值。
public static class AlgCode033Solution
{
public sealed class MinStack
{
private readonly Stack<(int Value, int Min)> _items = new();
public void Push(int value)
{
int min = _items.Count == 0
? value
: Math.Min(value, _items.Peek().Min);
_items.Push((value, min));
}
public int Pop() => _items.Pop().Value;
public int Top() => _items.Peek().Value;
public int GetMin() => _items.Peek().Min;
}
public static MinStack Solve() => new();
}复杂度： 每个操作时间 O(1)，n 个元素使用 O(n) 空间。
边界用例： 重复最小值；负数；只剩一个元素。
面试追问：
- 如何只在最小值变化时压入辅助栈并正确处理重复值？
034 使用两个栈实现先进先出的队列。
难度： 基础
方法签名： StackQueue Create()
输入约束： 调用 Dequeue 与 Peek 前队列非空
示例： Enqueue(1), Enqueue(2), Dequeue() → 1
目标复杂度： 各操作摊还 O(1)
查看参考答案
解题思路： 入队写入输入栈；输出栈为空时一次性倒入所有元素。
不变量： 输出栈顶部始终是当前最早入队且尚未出队的元素。
public static class AlgCode034Solution
{
public sealed class StackQueue
{
private readonly Stack<int> _input = new();
private readonly Stack<int> _output = new();
public void Enqueue(int value) => _input.Push(value);
public int Dequeue()
{
MoveIfNeeded();
return _output.Pop();
}
public int Peek()
{
MoveIfNeeded();
return _output.Peek();
}
public int Count => _input.Count + _output.Count;
private void MoveIfNeeded()
{
if (_output.Count > 0) return;
while (_input.Count > 0) _output.Push(_input.Pop());
}
}
public static StackQueue Solve() => new();
}复杂度： 每个元素最多在两个栈间移动一次，各操作摊还 O(1)，空间 O(n)。
边界用例： 连续入队；交替入队出队；输出栈非空时不能重复搬移。
面试追问：
- 为什么一次 Dequeue 可能是 O(n)，仍可称为摊还 O(1)？
035 计算合法逆波兰表达式的整数结果。
难度： 进阶
方法签名： string[] tokens
输入约束： 表达式合法，除法按 C# 整数除法向零截断
示例： [“2”,“1”,”+”,“3”,”*”] → 9
目标复杂度： 时间 O(n)，额外空间 O(n)
查看参考答案
解题思路： 数字入栈，运算符弹出右、左操作数并把结果压回。
不变量： 栈保存已处理前缀中尚未被后续运算消费的值。
public static class AlgCode035Solution
{
public static int Solve(string[] tokens)
{
var stack = new Stack<int>();
foreach (string token in tokens)
{
if (int.TryParse(token, out int value))
{
stack.Push(value);
continue;
}
int right = stack.Pop();
int left = stack.Pop();
stack.Push(token switch
{
"+" => left + right,
"-" => left - right,
"*" => left * right,
"/" => left / right,
_ => throw new ArgumentException("未知运算符。"),
});
}
return stack.Pop();
}
}复杂度： 时间 O(n)，额外空间 O(n)。
边界用例： 负数；减法与除法顺序；结果溢出按题目契约处理。
面试追问：
- 如何在输入可能非法时返回带错误位置的结果？
036 返回每个元素右侧第一个更大元素，不存在时返回 -1。
难度： 进阶
方法签名： int[] numbers
输入约束： numbers 非 null
示例： [2,1,2,4,3] → [4,2,4,-1,-1]
目标复杂度： 时间 O(n)，额外空间 O(n)
查看参考答案
解题思路： 维护值单调递减的未决下标栈，遇到更大值时结算。
不变量： 栈中下标对应值从底到顶单调不增，答案尚未确定。
public static class AlgCode036Solution
{
public static int[] Solve(int[] numbers)
{
int[] result = Enumerable.Repeat(-1, numbers.Length).ToArray();
var stack = new Stack<int>();
for (int index = 0; index < numbers.Length; index++)
{
while (stack.Count > 0 &&
numbers[stack.Peek()] < numbers[index])
result[stack.Pop()] = numbers[index];
stack.Push(index);
}
return result;
}
}复杂度： 时间 O(n)，额外空间 O(n)。
边界用例： 空数组；严格递减；重复值；最后元素。
面试追问：
- 如果数组是循环数组，如何在不复制数组的情况下处理？
037 返回每一天等待更高温度所需的天数。
难度： 进阶
方法签名： int[] temperatures
输入约束： temperatures 非 null
示例： [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]
目标复杂度： 时间 O(n)，额外空间 O(n)
查看参考答案
解题思路： 使用温度单调递减的下标栈，当前温度结算更低日期。
不变量： 栈中日期尚未找到更高温度，温度从底到顶单调不增。
public static class AlgCode037Solution
{
public static int[] Solve(int[] temperatures)
{
var result = new int[temperatures.Length];
var stack = new Stack<int>();
for (int day = 0; day < temperatures.Length; day++)
{
while (stack.Count > 0 &&
temperatures[stack.Peek()] < temperatures[day])
{
int previous = stack.Pop();
result[previous] = day - previous;
}
stack.Push(day);
}
return result;
}
}复杂度： 时间 O(n)，额外空间 O(n)。
边界用例： 空数组；持续下降；相同温度不算更高。
面试追问：
- 温度值域很小时能否从右向左用数组记录下一次出现位置？
038 求柱状图中可以形成的最大矩形面积。
难度： 综合
方法签名： int[] heights
输入约束： heights 非 null 且元素非负
示例： [2,1,5,6,2,3] → 10
目标复杂度： 时间 O(n)，额外空间 O(n)
查看参考答案
解题思路： 维护高度递增栈，遇到更低高度时结算以弹出柱为最矮柱的矩形。
不变量： 栈中下标对应高度严格递增，尚未遇到其右侧更小边界。
public static class AlgCode038Solution
{
public static long Solve(int[] heights)
{
var stack = new Stack<int>();
long best = 0;
for (int index = 0; index <= heights.Length; index++)
{
int current = index == heights.Length ? 0 : heights[index];
while (stack.Count > 0 && heights[stack.Peek()] > current)
{
int height = heights[stack.Pop()];
int left = stack.Count == 0 ? -1 : stack.Peek();
long width = index - left - 1L;
best = Math.Max(best, height * width);
}
if (index < heights.Length) stack.Push(index);
}
return best;
}
}复杂度： 时间 O(n)，额外空间 O(n)，面积使用 long。
边界用例： 空数组；全零；严格递增；严格递减；面积超过 int。
面试追问：
- 为什么弹栈后的新栈顶就是当前柱子的左侧更小边界？