计算几何实战：从“长城烽火台”问题看单调栈的3种典型应用
计算几何实战：从“长城烽火台”问题看单调栈的3种典型应用
在算法竞赛和实际工程问题中，单调栈（Monotonic Stack）是一种高效处理序列单调性问题的数据结构。本文将以PAT甲级真题“L3-009 长城”为切入点，深入解析单调栈在三种不同场景下的应用模式，包括凸包维护、区间极值求解和温度跨度计算。通过对比代码模板和动画演示思路，帮助读者掌握这一数据结构的灵活运用。
1. 问题背景与数学模型抽象
烽火台选址问题源自古代军事防御需求，现代计算几何中可抽象为二维平面点集的凸包维护。题目给定从南到北排列的N个折线顶点坐标（3≤N≤1e5），要求在最少的烽火台布置下，确保每个烽火台能向北监视所有未被山体遮挡的区域。
关键约束条件：
- 视线判定规则：若点B位于点A与点C的连线下方（即形成凹点），则B需要设置烽火台
- 数学表达：当斜率(AB) ≥ 斜率(BC)时，B为凹点
- 输入样例的几何解释：
(67,32) —— (48,-49) —— (32,53) —— (22,-44) —— (19,22) 凸点 凹点 凸点
该问题可转化为维护上凸壳（Upper Convex Hull），这与经典算法Andrew's Monotone Chain有异曲同工之妙。通过单调栈维护当前凸包点集，每次新点加入时检查是否需要弹出栈顶破坏凸性的点。
2. 单调栈的三种应用模式对比
2.1 模式一：凸包维护（本题应用）
核心操作：
- 按x坐标排序后顺序处理
- 维护栈内相邻三点斜率单调递减
- 遇到破坏单调性的点则弹出栈顶
bool isConcave(int l, int mid, int r) { return (Y[r]-Y[l])*(X[mid]-X[l]) >= (Y[mid]-Y[l])*(X[r]-X[l]); } void solve() { stack<int> st; for(int i=0; i<n; ++i) { while(st.size()>1 && isConcave(i, st.top(), st.second_top())) { st.pop(); } if(!st.empty()) updateAnswer(st.top()); st.push(i); } }2.2 模式二：柱状图最大矩形（LeetCode 84）
问题差异：
- 目标变为寻找左右第一个小于当前值的位置
- 维护栈内高度单调递增
int largestRectangleArea(vector<int>& heights) { stack<int> st; int maxArea = 0; heights.push_back(0); // 哨兵 for(int i=0; i<heights.size(); ){ if(st.empty() || heights[i]>heights[st.top()]){ st.push(i++); } else { int h = heights[st.top()]; st.pop(); int w = st.empty() ? i : i-st.top()-1; maxArea = max(maxArea, h*w); } } return maxArea; }2.3 模式三：每日温度（LeetCode 739）
问题特点：
- 需要计算每个元素到下一个更大元素的跨度
- 维护严格单调递减栈
vector<int> dailyTemperatures(vector<int>& T) { stack<int> st; vector<int> res(T.size()); for(int i=0; i<T.size(); ++i){ while(!st.empty() && T[i]>T[st.top()]){ res[st.top()] = i - st.top(); st.pop(); } st.push(i); } return res; }三种模式对比表
| 特征 | 凸包维护 | 柱状图最大矩形 | 每日温度 |
|---|---|---|---|
| 栈内单调性 | 斜率递减 | 高度递增 | 温度递减 |
| 弹出条件 | 新点破坏凸性 | 新点≤栈顶 | 新点>栈顶 |
| 典型操作 | 斜率比较 | 宽度计算 | 跨度计算 |
| 时间复杂度 | O(n) | O(n) | O(n) |
| 空间复杂度 | O(n) | O(n) | O(n) |
3. 算法优化与细节处理
3.1 数值稳定性优化
原始斜率比较存在浮点精度问题，改用交叉相乘形式：
// 原始版本（存在精度风险） bool check = (y2-y1)/(x2-x1) >= (y3-y2)/(x3-x2); // 优化版本 bool check = (y2-y1)*(x3-x2) >= (y3-y2)*(x2-x1);3.2 边界条件处理
- 总部处理：第一个顶点不参与计算
- 共线情况：根据题意视为可监视
- 大数据量：使用数组模拟栈减少STL开销
int st[N], top = 0; // 数组模拟栈 for(int i=0; i<n; ++i){ while(top>1 && isConcave(i, st[top-1], st[top-2])) top--; if(top>0 && !vis[st[top-1]]) { vis[st[top-1]] = 1; ans++; } st[top++] = i; }4. 变式训练与思维拓展
4.1 变式一：三维凸包
若烽火台需考虑海拔高度，问题升级为三维凸包。此时需使用增量法（O(n²)）或分治法（O(nlogn)）。
4.2 变式二：动态维护
支持在线插入和删除点，可采用平衡树维护凸包，每次操作O(logn)时间。
4.3 变式三：最小烽火台环
将问题改为环形布置时，可通过破环为链+滑动窗口解决。
提示：所有变式练习题的解法和测试数据可在PAT官方题库或Codeforces几何专题中找到类似题目
5. 可视化理解工具
理解凸包维护过程的关键在于动态演示：
- 初始状态：空栈，按x坐标排序的点集
- 加入过程：用不同颜色标注被保留和弹出的点
- 最终结果：连接栈内剩余点形成凸包
推荐使用GeoGebra或Desmos进行交互式演示，调整点集观察凸包变化规律。对于栈操作过程，可用VisuAlgo的栈动画模块辅助理解。
在实际编码调试时，可输出中间状态帮助验证：
def print_stack(st, points): print("Current Stack:", [(points[i].x, points[i].y) for i in st])掌握单调栈的核心在于识别问题中的单调性需求，通过大量练习培养对三种应用模式的直觉判断。建议读者从经典问题入手，逐步过渡到结合线段树、二分查找等高级技巧的复合题型。