单调栈结构

[编程题]单调栈结构

热度指数：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

输出

备注:

算法知识视频讲解

Python3

halehale

n = int(input())
arr = list(map(int, input().split(' ')))

res = [0]*n
stack = []
for i in range(n):
    while stack and arr[stack[-1]]>arr[i]:
        pop_index = stack.pop()
        if stack:
            left_less_index = stack[-1]
        else:
            left_less_index = -1
        res[pop_index] = [left_less_index, i]
    stack.append(i)
        
while stack:
    pop_index = stack.pop()
    if stack:
        left_less_index = stack[-1]
    else:
        left_less_index = -1
    res[pop_index] = [left_less_index, -1]

for j in res:
    print(str(j[0]) + ' ' + str(j[1]))

发表于 2021-11-09 23:28:10 回复(0)