给定一个数组，找出每个元素的最后一个小于它的元素。

Question

给定一个数组，找出每个元素在数组中最后一个比它小的数的索引。

例如，假设给定的数组为{4,2,1,5,3}。那么每个元素的最后一个较小元素将如下所示。

4->3
2->1
1->Null
5->3
3->Null

第一对4->3的注意事项，3是数组中小于4的最后一个元素。

输出数组将具有索引而不是元素本身。结果将是 {4,2,-1,4,-1}

我在面试中被问到这个问题，但我想不出比平凡的 O(n^2) 解决方案更好的解决方法。

任何帮助都将不胜感激。

- faizan

Answer 1

我们需要计算所有比当前元素小的元素中最大的索引max(index)。

让我们按字典顺序对元素和索引的对进行排序，并迭代它们，同时跟踪迄今为止看到的最大索引。这正是右侧较小元素的位置。下面是实现方法:

def get_right_smaller(xs):
    res = [-1] * len(xs)
    right_index = -1
    for val, idx in sorted((val, idx) for idx, val in enumerate(xs)):
        res[idx] = right_index if right_index > idx else -1
        right_index = max(right_index, idx)
    return res

即使输入的数组包含相等的数字，该解决方案也可以正常工作，因为如果两个元素的值相同，则具有较小索引的元素先出现。

此解决方案的时间复杂度为O(N log N + N) = O(N log N)（进行排序和一次线性遍历）。

如果数组的所有元素都是O(N)，则可以使用计数排序使此解决方案变为线性。

- kraskevich

---

很棒的解决方案！ - גלעד ברקן

Answer 2

Make a list, add last element index. 
Walk through array right to left.     
For every element:
   if list tail value is smaller then current element
       find the most first smaller list element (binary search, list is sorted)
   otherwise 
       add element index to the list tail, output -1

对于例子列表 {4,2,1,5,3,6,2}，结果列表将包含 索引 6（值为 2）；索引 2（值为 1）。

- MBo

---

以一个示例数组为例 - {4,2,1,5,3,6,2}。当我从右边处理时。 添加3、6、2后 - 3(根) 2(左) 6(右)现在，在添加3,6,2之后，对于元素5，我们将查看树（在插入5之前）。存在2个较小的值-3和2。正确的选择值是2，但如果我使用floor函数，则会给我3。 那么我们如何选择较小的值呢？ - faizan

似乎我对“最后一个较小元素”的条件理解有误。 - MBo

新增了新的方法。 - MBo