[编程题]逛街

腾讯后端校招题目

链接：https://www.nowcoder.com/questionTerminal/35fac8d69f314e958a150c141894ef6a

来源：牛客网

热度指数：7656时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M

小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述:

输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。

1<=n<=100000;
1<=wi<=100000;

输出描述:

输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。示例1

输入

6
5 3 8 3 2 5

输出

3 3 5 4 4 4

说明

当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

First Try

2020-10-08

一开始真是毫无思路，想的是以前的积木盛水的套路，但是单靠左右两边最高点，根本无法统计前面能看到多少栋楼。

看题解才知道，这又是传统套路单调栈。

对于每栋楼的位置，看左右两边的楼，能看到的都是维持一个单调递减的状态。前面的单调栈有多少个元素，就能看到多少栋楼，并不取决于当前楼的高度。额外添加当前楼的时候，需要把已有的栈中比当前楼低的元素都剔除掉，然后才得到结果。

向左看和向右看的单调栈都需要加上去，然后再加上当前楼，就搞定了。

感觉很久没写代码题，整个思路都是缓慢的，在mac小屏幕上写起来更是别扭。

n = int(input())
bs = [int(i) for i in input().split()]

rv = [1] * n 
lstack = [] 
rstack = []
for i in range(n):
    rv[i] += len(lstack)
    while len(lstack) and lstack[-1] <= bs[i]:
        lstack.pop()
    lstack.append(bs[i])
    
    j = n - 1 - i 
    rv[j] += len(rstack)
    while len(rstack) and rstack[-1] <= bs[j]:
        rstack.pop()
    rstack.append(bs[j])

print(' '.join([str(i) for i in rv]))

[编程题]逛街​

First Try​

[编程题]逛街

First Try