单调栈

题号：NC217405
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 $n$ 的可能含有重复值的数组 $nums$ ，找到每一个位置 $i$ 左边最近的位置 $l$ 和右边最近的位置 $r$ ， $nums_l$ 和 $nums_r$ 比 $nums_i$ 小。

请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 $l$ 和 $r$ 。如果不存在，则值为 -1，下标从 0 开始。

数据范围： $1 \le n \le 10^5$ ， $-10^9 \le nums_i \le 10^9$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

复制

[3,4,1,5,6,2,7]

复制

[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]

示例2

复制

[1,1,1,1]

复制

[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]