这道题的正解是 单调栈,但是我们用朴素解法 向右扫描找第一个更高建筑 也能在考试时拿到一定的分数。
题意:对每个建筑 i,向右看的「安全视野距离」等于:从 i+1 起连续能看到的建筑个数。能看到的规则是——一直看到(并包含)右侧第一个严格更高的建筑;若右侧没有更高建筑,则能看到右边全部剩余建筑。相同高度不遮挡。
等价写法:若右侧存在第一个严格大于 hi 的位置 j,答案为 j−i;否则答案为 n−1−i。
朴素做法:对每个位置 i,从 i+1 向右扫,直到找到更高建筑或扫到末尾。时间 O(n2)。
在城市规划中,建筑师需要分析建筑物之间的视野关系。给出一条街道上的一排建筑物,每个建筑物有一定的高度。对于每个建筑物,我们定义一个安全视野距离:从该建筑物向右看,能看到的建筑物的数量。
一个建筑物 A 能够看到另一个建筑物 B 的条件是:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.