我要招人

去企业版

首页 > 试题广场 >

单调栈

[编程题]单调栈

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

给定一个长度为 $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]]

算法知识视频讲解

mlpan

发表于 2021-04-22 09:47:45

单调栈典型的单调栈的思想做题 public int[][] foundMonotoneStack (int[] nums) { // write code here int len = nums.length; // 返回的数组构造展开全文

泪无声呢

发表于 2021-07-29 17:58:24

单调栈问题描述：给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括：两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。示例输入：[3,4,1,5,6,2,7 展开全文

棒棒糖🍭201906101800876

发表于 2021-07-29 16:11:48

NC157 单调栈题意给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比小的位置。 1. 暴力做法按照题意，两重循环模拟即可。 class Solution { public: /** * 代码中的类名、方法名、参数展开全文

牛客500979850号

发表于 2021-10-07 21:43:17

题意：给定一个数组（可含重复值），找到每个元素左边和右边比它小且离它最近的数组位置。方法一：暴力解法解题思路：对于每个元素，都向左和向右找比它小的即可。代码如下： public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可展开全文

牛客245120908号

发表于 2022-02-25 15:16:34

思路：当前数分别跟左边和右边比一遍，获取第一个小的值下标 1.循环比较赋值，就是时间复杂度有点高时间复杂度 n^2 空间复杂度 1个二维数组 2个常量 import java.util.*; public class Solution { /** * 代码中的类名、方展开全文

非逆

发表于 2022-03-31 13:03:10

只需一次遍历： class Solution: def foundMonotoneStack(self , nums: List[int]) -> List[List[int]]: stack = [] ans = [[-1, -1] for _ in 展开全文

摸鱼学大师

发表于 2021-12-09 19:29:36

题目的主要信息：给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置结果返回一个二维数组，表示所有位置相应的信息，如果找不到位置，则相应地方为-1 下标0开始进阶要求：空间复杂度 O(n)O(n)O(n) ，时间复展开全文