对于数组中的每个数字,请从其左侧找到第一个较小的数字

我一直在思考这个问题好几个小时,到目前为止,我的每个想法都不好。

执行此操作的函数将接收原始数组和需要填充的空数组。

如果某个对象没有这样的索引,则应插入-1。

例如,对于数组:[4,6,8,1,7,10,15,9,11]数组[-1,1,-1,3,4,5,4,应该返回7],因为例如,如果我们看原始数组中的9,则从它左边开始的第一个较小的数字是7,而索引7是4。因此,应代替原始数组中的9,填写新的。

如果原始数组的大小为n,则我的时间复杂度为O(n),空间复杂度也为O(n)。

您只能使用数组或列表来获取帮助,而不能使用其他结构。

这是我到目前为止收集的内容: 1.对数组进行排序,以及无法明确解决问题的解决方案。

  1. 如果我们开始从左到右查看数组,一旦发现一个小于其他数字的数字,就可以扔掉“其他”数字。我相信这是最重要的事情,但是我无法使用它。

  2. 将原始数组分割为排序的微型数组无济于事。

Jason82918 回答:对于数组中的每个数字,请从其左侧找到第一个较小的数字

创建一个堆栈(基于数组或列表:)。它将保留候选元素的索引。

遍历源数组。

如果当前元素大于堆栈顶部寻址的元素,则将堆栈顶部复制到输出数组中,并将当前索引推入堆栈。

如果通过堆栈顶部寻址的元素较大,则弹出堆栈,直到找到较小的元素为止。

我省略了一些自己认识的时刻。

请注意,堆栈每时每刻都包含递增顺序的索引。

本文链接:https://www.f2er.com/3100059.html

大家都在问