计算几何实战：从“长城烽火台”问题看单调栈的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 模式一：凸包维护（本题应用）

核心操作：

1. 按x坐标排序后顺序处理
2. 维护栈内相邻三点斜率单调递减
3. 遇到破坏单调性的点则弹出栈顶

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; }

三种模式对比表

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. 可视化理解工具

理解凸包维护过程的关键在于动态演示：

1. 初始状态：空栈，按x坐标排序的点集
2. 加入过程：用不同颜色标注被保留和弹出的点
3. 最终结果：连接栈内剩余点形成凸包

推荐使用GeoGebra或Desmos进行交互式演示，调整点集观察凸包变化规律。对于栈操作过程，可用VisuAlgo的栈动画模块辅助理解。

在实际编码调试时，可输出中间状态帮助验证：

def print_stack(st, points): print("Current Stack:", [(points[i].x, points[i].y) for i in st])

掌握单调栈的核心在于识别问题中的单调性需求，通过大量练习培养对三种应用模式的直觉判断。建议读者从经典问题入手，逐步过渡到结合线段树、二分查找等高级技巧的复合题型。