单调栈算法解析：解决视线遮挡问题的高效方案

1. 题目背景与问题解析这道来自COI 2007的编程竞赛题目描述了一个有趣的现实场景在Patrik的音乐会现场N个人正排成一列等待入场。题目要求我们计算在这些人群中有多少对人能够互相看到对方。这里的互相看到定义为两个人之间没有比他们更高的人阻挡视线。从数据结构的角度来看这实际上是一个经典的单调栈应用问题。我们需要处理的是一个高度序列寻找满足特定条件的数对。这类问题在编程竞赛中非常典型也常出现在大厂算法面试中。2. 算法思路分析2.1 暴力解法及其局限性最直观的解法是双重循环遍历所有可能的人对(i,j)然后检查他们之间是否有更高的障碍。这种方法的时间复杂度是O(n²)对于n≤500,000的数据规模来说完全不可行会导致超时。提示在算法竞赛中通常认为1秒内能处理的运算量级在10^7左右。对于n5×10^5n²2.5×10^11远超合理范围。2.2 单调栈的引入我们需要一种更高效的算法这时单调栈就派上用场了。单调栈是指栈内元素保持单调递增或递减的栈结构特别适合处理下一个更大元素这类问题。在这个问题中我们可以维护一个单调递减栈栈内存储的是人的高度和相同高度的计数。当我们处理一个新元素时通过栈的结构可以快速找到能看到当前元素的所有前面的人。2.3 算法正确性证明算法的正确性基于以下观察如果当前人比栈顶人高那么栈顶人能看到当前人且之后的人会被当前人挡住视线如果当前人与栈顶人等高他们可以互相看到且不影响后面人的视线判断如果当前人比栈顶人矮只能看到栈顶人需要保留栈顶人以判断后续的人3. 详细实现步骤3.1 初始化设置#include iostream #include stack using namespace std; typedef pairint, int pii; // 存储高度和计数 stackpii st; long long ans 0; // 使用long long防止溢出3.2 主算法流程int main() { int n, h; cin n; for(int i 0; i n; i) { cin h; pii p {h, 1}; // 处理栈顶比当前矮的情况 while(!st.empty() st.top().first h) { ans st.top().second; if(st.top().first h) { p.second st.top().second; } st.pop(); } // 如果栈不空还能多看到一个人 if(!st.empty()) { ans; } st.push(p); } cout ans endl; return 0; }3.3 关键步骤解释输入处理读取每个人的高度h栈维护保持栈的单调递减性弹出所有小于等于当前h的元素对于每个弹出的元素增加答案计数如果遇到相等高度合并计数额外计数如果栈非空当前人还能看到栈顶的人入栈操作将当前人(可能合并后的)信息压入栈中4. 复杂度分析与优化4.1 时间复杂度每个元素最多入栈和出栈一次因此时间复杂度是O(n)完美适合题目给出的数据规模。4.2 空间复杂度最坏情况下所有元素都在栈中空间复杂度是O(n)。4.3 常数优化技巧使用C的iostream并关闭同步可以加快输入输出速度使用pairint,int而不是结构体可以减少内存访问时间在竞赛中使用数组模拟栈有时比STL stack更快5. 边界情况与测试用例5.1 常见边界情况所有人高度相同[5,5,5,5] → 答案应为6严格递增序列[1,2,3,4] → 答案应为3严格递减序列[4,3,2,1] → 答案应为6单峰序列[1,2,3,2,1] → 答案应为7空输入或单元素输入答案应为05.2 测试用例设计技巧在设计测试用例时应该考虑大数据量测试(验证时间效率)极端值测试(如高度全部相同)随机生成测试(验证算法鲁棒性)特殊模式测试(如锯齿形高度变化)6. 算法扩展与变种6.1 类似问题柱状图中的最大矩形(LeetCode 84)接雨水问题(LeetCode 42)每日温度(LeetCode 739)滑动窗口最大值(LeetCode 239)6.2 变种问题思考如果要求计算三元组(i,j,k)的数量其中ijk且i和k能互相看到该如何解决如果视线可以被多个等高的人阻挡算法需要如何修改如果队伍是环形排列的算法该如何调整7. 竞赛实战技巧7.1 调试技巧对于栈类算法可以在关键步骤打印栈内容使用小规模测试用例手工验证比较暴力解法和优化解法的结果是否一致7.2 编码注意事项注意ans要使用long long类型避免溢出注意处理相等高度的合并计数栈操作前一定要检查是否为空输入输出使用快速方法避免超时7.3 常见错误忘记处理高度相等的情况没有考虑最后栈中剩余的元素数据类型不够大导致溢出输入输出效率不足导致超时8. 实际应用场景虽然题目设定在音乐会排队场景但这类算法在实际中有广泛应用城市天际线分析无线信号塔覆盖范围计算股票分析中的支撑位/阻力位识别地理信息系统中的视线分析掌握单调栈不仅对算法竞赛有帮助也是解决许多实际工程问题的重要工具。理解其核心思想后可以灵活应用到各种需要处理序列中元素相对大小关系的场景中。