计算几何实战：从“长城烽火台”问题看单调栈的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这与经典算法Andrews 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() { stackint st; for(int i0; in; 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(vectorint heights) { stackint st; int maxArea 0; heights.push_back(0); // 哨兵 for(int i0; iheights.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问题特点需要计算每个元素到下一个更大元素的跨度维护严格单调递减栈vectorint dailyTemperatures(vectorint T) { stackint st; vectorint res(T.size()); for(int i0; iT.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 i0; in; i){ while(top1 isConcave(i, st[top-1], st[top-2])) top--; if(top0 !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])掌握单调栈的核心在于识别问题中的单调性需求通过大量练习培养对三种应用模式的直觉判断。建议读者从经典问题入手逐步过渡到结合线段树、二分查找等高级技巧的复合题型。