会员专享
请先
登录,登录后可使用今日免费解锁;
开通会员后可解锁完整内容。
扫描朴素解法
这道题的正解是 单调栈,但是我们用朴素解法 向右扫描找第一个更高建筑 也能在考试时拿到一定的分数。
题意:对每个建筑 i,向右看的「安全视野距离」等于:从 i+1 起连续能看到的建筑个数。能看到的规则是——一直看到(并包含)右侧第一个严格更高的建筑;若右侧没有更高建筑,则能看到右边全部剩余建筑。相同高度不遮挡。
等价写法:若右侧存在第一个严格大于 hi 的位置 j,答案为 j−i;否则答案为 n−1−i。
朴素做法:对每个位置 i,从 i+1 向右扫,直到找到更高建筑或扫到末尾。时间 O(n2)。