星际信号塔 —— 单调栈经典应用详解

题目名称星际信号塔【题目背景】在未来的星际开拓中人类在X星球上建立了一排用于深空通信的信号塔由于星球曲率影响较小我们可以将它们视为建立在一条直线上。【题目描述】X 星球的地表上从西向东依次排列着n座信号塔编号依次为1到n。第i座信号塔的高度为。为了进行星际广播每座信号塔都会向正东方向即编号增大的方向发射定向电磁波。但是电磁波是沿直线传播的如果前方有比发射塔严格更高的信号塔电磁波就会被那一座信号塔完全阻挡并吸收。现在星际工程局需要进行网络拓扑分析。请你计算对于每一座信号塔它的信号会被东方哪一座信号塔阻挡请输出阻挡它的第一座更高信号塔的编号。如果它的前方没有任何比它高的信号塔它的信号将顺利射向深空此时请输出0。【输入格式】第一行包含一个正整数n表示信号塔的总数量。第二行包含n个正整数相邻两个数之间用单个空格隔开表示从西向东每座信号塔的高度。【输出格式】输出一行包含n个整数。第i个整数表示阻挡第i座信号塔信号的信号塔编号如果没有被阻挡则输出0。相邻两个整数之间用单个空格隔开。【样例输入】7 2 6 3 1 5 7 4【样例输出】2 6 5 5 6 0 0【数据规模与约定】对于的数据保证。题目分析本题的核心诉求是在一个由数字组成的序列中针对每一个元素寻找它右侧第一个严格大于它的元素的下标。如果右侧不存在更大的元素则返回0。虽然题目披上了“星际信号塔”和“电磁波阻挡”的科幻外衣但剥去场景包装后这道题是经典的“下一个更大元素”问题是学习数据结构中单调栈的必刷模板题。思考过程暴力求解超时最直观的想法是使用双重for循环。对于每一座信号塔i都向后遍历j(从i1到n)找到第一个满足h[j]h[i]的j。缺陷数据规模n最大为200,000。暴力解法的时间复杂度是O(n^2)极端情况下如信号塔高度单调递减会进行上百亿次比较必然会导致超时。寻找优化空间我们需要一种O(n)的解法。观察发现如果遇到一座非常高的塔那么它前面那些比较矮的塔的“视线”都会被它挡住。此时那些矮塔的答案就确定了。 因此我们可以把那些“还没找到阻挡者”的塔先“存起来”。一旦遇到一座新塔就回头看看存起来的塔里面有哪些矮塔是被这座新塔挡住的。解题思路与算法设计为了实现上述优化我们引入单调栈栈内存储的是信号塔的下标为了方便记录答案以及通过下标查找高度。栈内下标对应的信号塔高度从栈底到栈顶必须是严格递减或非递增的。具体算法步骤建立一个空栈s和一个结果数组a。从左到右遍历每一座信号塔i比较与出栈如果栈不为空且当前塔的高度h[i]严格大于栈顶下标对应的塔的高度h[s.top()]说明当前塔i就是阻挡栈顶塔的“第一座高塔”。 将结果记录到数组a[s.top()]i然后将栈顶元素弹出。 重复此过程直到栈为空或者当前塔不再高于栈顶塔。入栈将当前塔的下标i压入栈中等待后续更高的塔来阻挡它。收尾遍历结束后栈内剩下的下标对应的塔意味着它们右侧没有任何比它们更高的塔。将它们的答案设置为0并弹出。时空复杂度分析时间复杂度O(n)虽然代码中有一个for循环嵌套了while循环但仔细分析会发现每一座信号塔的下标最多入栈1次出栈1次。整体来看while循环内部的执行次数总量不超过n。因此平摊到每次操作时间复杂度为线性的O(n)。空间复杂度O(n)最坏情况下如给定的塔高度单调递减所有塔都会入栈且不被弹出此时栈占用的空间为O(n)。同时我们使用了一个大小为n的数组记录结果和高度。综合空间复杂度为O(n)。学生易错点总结栈内存下标还是存高度这是初学者最容易犯的错误。栈中必须存下标因为题目要求输出的是阻挡塔的编号即下标且我们需要通过下标去更新结果数组a[s.top()]i。比较时的低级失误在while循环中千万不要写成h[i]s.top()。s.top()是下标h[s.top()]才是高度必须用高度和高度比较。全局数组的特性在C中定义在main函数外的全局数组默认初始化全为0。虽然利用这个特性可以省去最后一步清空栈并赋值为0的操作但为了算法逻辑的严密性和可移植性建议手动将残余栈顶元素的答案置为0。完整代码//星际信号塔 #include iostream #include stack using namespace std; int n; stackint s;//单调栈 用于存储塔的下标编号 int a[200010];//a[i]代表阻挡i的第一座比i更高的信号塔 int h[200010];//存每座塔高度 int main() { cinn; for(int i1;in;i) cinh[i]; for(int i1;in;i){//遍历n座塔 //当栈不为空且当前塔高度超过栈顶塔时 //说明我们找到了栈顶塔的“阻挡者” while(!s.empty()h[i]h[s.top()]){ a[s.top()]i;//记录比栈顶塔高的第一座塔是i号塔 s.pop();//栈顶塔找到答案 出栈 } //直到栈空或当前塔小于栈顶塔高度时把当前塔入栈 s.push(i); } //结束后要把栈内剩下的都出栈 //剩下的塔前方都不存在比它高的塔 while(!s.empty()){ a[s.top()]0; s.pop(); } for(int i1;in;i) couta[i] ; return 0; }