查找数组中每个元素的最后一个较小或相等的数字？

Question

我得到了一个数组。我需要为数组中的每个元素找到最后一个（最右边的）较小或相等的数字。

例如：

2 5 1 6 4 7

2的最后一个小于或等于
1，5的最后一个小于或等于4，而不是1，依此类推。

另一个例子：

5 100 8 7 6 5 4 3 2 1

在这里，每个元素的最后一个较小或等于1。我知道简单的方法，即O（n²），但是需要更好的方法。

Answer 1

您可以从右到左构建一个最小数量的最小数组，直到现在。对于您的示例2 5 1 6 4 7，它将是：从最右边的位置开始：

7
4 7    (4 < 7)
4 4 7  (6 > 4)
...

因此，您的示例的min数组为： 1 1 1 4 4 7

现在，对于每个查询，您都将从min数组中的相同位置开始，然后一直继续直到找到一个更大的数字：

对于2：

2 5 1 6 4 7
1 1 1 4 4 7
^
------^

第一个大于2的元素为4，因此返回数字等于1

对于5：

2 5 1 6 4 7
1 1 1 4 4 7
  ^
----------^

大于5的第一个元素是7，因此返回数字= 4

为了有效地为输入数组中的每个元素找到更大的第一个元素，可以使用upper_bound算法（在C ++中的示例http://www.cplusplus.com/reference/algorithm/upper_bound/）来查找更大的第一个元素

Upper_bound需要log（N）时间，因此处理输入数组中每个元素的总时间为O（NlogN）

最小数组的内存复杂度是线性的