逛街

[编程题]逛街

热度指数：9251 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。

小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述:

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

输出描述:

输出一行，包含空格分割的n个数字v_i，分别代表小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栋楼。

算法知识视频讲解

JavaScript

萌萌萌哒

JavScript 解法发现还没人用js做出来😳 自己创建一个Stack 实例，问题迎刃而解😎

JS（Node）

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 2){
        let n = +inArr[0]
        let nArr = inArr[1].split(' ').map(e=>+e)
        let left = [],
            right = [],
            total = []
        let stack =new Stack()
        for (let i = n-1; i>=0 ; i--) {
            right[i] = stack.length()
            while(right.length!=0 && nArr[i]>=nArr[stack.peek()]){
                stack.pop()
            }
            stack.push(i)  
        }
        stack.clear()
        for (let i = 0; i < n; i++) {
            total[i] = right[i] + stack.length()+1
            left[i] = stack.length()
            while(left.length!=0 && nArr[i]>=nArr[stack.peek()]){
                stack.pop()
            }
            stack.push(i) 
            
        }
        // console.log(right)
        // console.log(left)
        console.log(total.join(' '))

    }
})

function Stack() {
    this.dataStore=[]
    this.top = 0
    this.peek =peek
    this.pop =pop
    this.push =push
    this.length = length
    this.clear = clear
}
function push(e) {
    this.dataStore[this.top++] =e
}
function peek() {
    return this.dataStore[this.top-1]
}
function pop() {
    return this.dataStore[--this.top]
}
function clear() {
    this.top = 0
}
function length() {
    return this.top
}

发表于 2020-02-18 12:22:22 回复(0)