arrays - 为数组中的每个元素找到最后一个较小或相等的数字？

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)
...

因此您的示例的最小数组为:1 1 1 4 4 7

现在对于每个查询，您从最小数组中的相同位置开始并向右移动直到找到一个更大的数字:

对于 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)

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