如何使用堆栈找到Find max right？

Question

我正在解决这个问题，我们需要为给定数组 A 中的每个 A[i] 找到 rightSpecialValue。RightSpecialValue 定义如下。

RightSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] and (j>i). If multiple A[j]'s are present in multiple positions, the RightSpecialValue is the minimum value of j. Here RightSpecialValue is the index j and not A[j].

可以通过在 O(n) 中使用堆栈轻松解决，但是如果将其更改为“如果多个 A[j] 存在于多个位置，则 RightSpecialValue 是 j 的 maximum 值。这里 RightSpecialValue是索引 j 而不是 A[j]。”

还有比 O(n^2) 更好的解决方案吗？

Answer 1

是的，您可以通过创建一个最初为空并包含索引的候选列表来解决这个 O(nlogn) 的新问题。现在您向后看，对于每个索引 i，您通过二分找到最小的 a[j] > a[i]，其中 j 是候选列表中的索引（候选列表按升序排序）。如果您没有找到这样的索引，请将 i 添加到候选者中（并将 i 设置为 -1 或 null 或其他结果）。如果您在候选集 result[i] = j 中找到索引 j。