单调栈结构

[编程题]单调栈结构

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

给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

输入描述:

第一行输入一个数字 n，表示数组 arr 的长度。

以下一行输出 n个数字，表示数组的值。

输出描述:

输出n行，每行两个数字 L 和 R，如果不存在，则值为-1，下标从0开始。

示例1

输入

7
3 4 1 5 6 2 7

输出

备注:

算法知识视频讲解

JavaScript

Relili

今天真的去吃了【周末愉快】

let n=parseInt(readline()) 
let line=readline()
let arr=line.split(' ').map(item=>parseInt(item))

let res=Array.from({length:n},()=>[-1,-1])
let stack=[]
for(let i=0;i<n;i++){
    if(stack.length==0){
        stack.push(i)
    }else{

        while(arr[i]<=arr[stack[stack.length-1]]){
            var curIndex=stack.pop()
            res[curIndex][1]=i
        }
        if(stack.length)res[i][0]=stack[stack.length-1]
        stack.push(i)
    }
}
res.forEach(item=>console.log(item.join(' ')))

编辑于 2021-06-25 17:36:43 回复(0)