arrays - 练习面试题在array[j] >= array[i]的条件下要求max j-i;不懂解决办法

Question

我正在阅读这篇社论:https://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/我无法理解 O(n) 解决方案如何工作的解释。描述它的段落似乎与代码相矛盾。我已经检查了一个示例数组并手动确保这似乎有效，但对我来说它似乎根本不直观。

在解决编程难题方面更有经验的人是否愿意解释这是如何工作的以及为什么工作，或者解释它有什么问题？

谢谢。

(以下是上面链接中的文本:)

问题:

给定一个数组 arr[]，找到最大的 j – i 使得 arr[j] > arr[i] 给定一个数组 arr[]，找到最大的 j – i 使得 arr[j] > arr[i]。

例子:

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output: 6  (j = 7, i = 1)

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)

方法二(高效)

为了解决这个问题，我们需要得到arr[]的两个最优索引:左索引i和右索引j。对于一个元素arr[i]，如果arr[i]的左边有一个小于arr[i]的元素，我们就不需要考虑arr[i]作为左索引。同样，如果arr[j]的右边有一个更大的元素，那么我们就不需要考虑这个j作为右索引。所以我们构造两个辅助数组 LMin[] 和 RMax[] 使得 LMin[i] 保存 arr[i] 包括 arr[i] 左侧的最小元素，而 RMax[j] 保存 arr[i] 右侧的最大元素arr[j] 包括 arr[j]。构造完这两个辅助数组后，我们从左到右遍历这两个数组。在遍历 LMin[] 和 RMa[] 时，如果我们看到 LMin[i] 大于 RMax[j]，那么我们必须在 LMin[] 中向前移动(或执行 i++)，因为 LMin[i] 左侧的所有元素都是大于或等于 LMin[i]。否则我们必须在 RMax[j] 中向前移动以寻找更大的 j – i 值。

Answer 1

它有效。代码作者只是走了一条令人困惑的捷径。

正如社论所指出的，给定指数 i1 < i2与 arr[i1] ≤ arr[i2] , 没有必要考虑 i = i2 .我们总是可以通过设置 i = i1 来做得更好相反，因为对于所有 j ,

1. j - i1 > j - i2 , 和
2. 如果arr[j] > arr[i2] , 那么事实 arr[i2] ≥ arr[i1]暗示 arr[j] > arr[i1] .

类似地，给定索引 j1 < j2与 arr[j1] ≤ arr[j2] , 没有必要考虑 j = j1 .

让我们检查第一个样本输入并消除所有这些次优候选对象。

34  8  10  3  2  80  30  33  1
34  8      3  2              1  // candidate values of arr[i]
                 80      33  1  // candidate values of arr[j]

观察到两个子序列都减少了。这是作为候选人的上述条件的直接结果。

寻找最好的 i和 j现在涉及到一个编程竞赛陈词滥调。让我把各种可能性组织成一个表格。 请注意，该算法并未显式构造此表；它只是一种视觉辅助。

    80  33  1
-------------
34   √
 8   √   √
 3   √   √
 2   √   √
 1   √   √

复选标记 ( √ ) 表示 arr[i] < arr[j] .下降意味着增加i和减少 arr[i] .向左走意味着减少j并增加arr[j] .因此，只要有复选标记，下方或左侧的所有方 block 或某些组合也有复选标记。另一方面，给定一个带有复选标记的方 block 位于另一个带有复选标记的方 block 的下方/左侧，后一个方 block 必然是更好的解决方案，因为 i小于或等于 j更大或两者兼而有之。因此，我们对有复选标记和无复选标记之间的边界非常感兴趣，因为那是最优解所在。

追踪边界的算法很简单。从左上角的方 block 开始。如果当前方 block 有复选标记，请向右走。否则，下去。我希望您能了解此过程如何及时访问每列中的第一个复选标记 O(#rows + #columns) .这是另一个可能的表格。

    33  8  7  3
---------------
34
 8   √
 3   √  √  √
 2   √  √  √  √
 1   √  √  √  √

为了实现，请注意我们正在执行相同的搜索，但一些行/列被复制以填充非候选者留下的空白空间，从而省去了我们注意索引之间对应关系的麻烦。这基本上是相同的想法。