这道题的正解是 单调栈,但是我们用朴素解法 向右扫描找第一个更高建筑 也能在考试时拿到一定的分数。
题意:对每个建筑 i,向右看的「安全视野距离」等于:从 i+1 起连续能看到的建筑个数。能看到的规则是——一直看到(并包含)右侧第一个严格更高的建筑;若右侧没有更高建筑,则能看到右边全部剩余建筑。相同高度不遮挡。
等价写法:若右侧存在第一个严格大于 hi 的位置 j,答案为 j−i;否则答案为 n−1−i。
朴素做法:对每个位置 i,从 i+1 向右扫,直到找到更高建筑或扫到末尾。时间 O(n2)。
一条街道上依次排列着 n 个建筑物,每个建筑物都有对应的高度。现在需要从每个建筑物的位置向右观察,并计算它的安全视野距离,即该建筑物向右能够看到的建筑物数量。
对于任意建筑物 A,观察过程具有连续性:从 A 右侧相邻的建筑物开始依次向右观察。在遇到第一个高度严格大于 A 的建筑物之前,沿途的建筑物均处于 A 的视野中;这个第一个更高的建筑物本身也能够被 A 看到,但从它之后开始,更远处的所有建筑物都无法再被 A 看到。
因此,建筑物 A 能够看到其右侧的建筑物 B,需要满足以下规则:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册