在数组[j]>=数组[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]

例子：

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[j]的右侧保留最大的元素，包括arr[j]。在构造这两个辅助数组之后，我们从左到右遍历这两个数组。在遍历LMin[]和RMa[]时，如果我们看到LMin[i]大于RMax[j]，那么我们必须在LMin[]（或do i）中前进，因为LMin[i]左边的所有元素都大于或等于LMin[i]。否则，我们必须在RMax[j]中继续前进，以寻找更大的j–i值。

Answer 1

这是单调函数的魔力，也是一个人通过想象问题的解决方案空间以及这些值如何对齐而获得的洞察力。让我们在链接到的页面中绘制一个示例；x轴上的数组索引、y轴上的LMin和RMax：

  {34, 8,10, 3, 2,80,30,33, 1}
    0  1  2  3  4  5  6  7  8

80  r  r  r  r  r  r
 .
34  l
33                    r  r
 .                       ^
30
 .
10
 . 
 8     l  l
 .     ^
 3           l
 2              l  l  l  l
 1                         lr
    0  1  2  3  4  5  6  7  8

r值不一定是与数组索引相关联的值；相反，它表明我们可以将间隔向右侧延伸多远，保证右侧的nor会更大（这意味着我们可能会错过更大的间隔）。类似地，l表示我们处于左向最小值，并且由于我们首先探索沿着rs移动，我们保证在搜索的任何时间间隔内都不会错过先前的l。显然，我们最多沿着所有rs和所有ls从左到右迭代，所以O（n）。

Answer 2

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

正如社论所指出的，给定的指数i1

1. j-i1

同样，给定索引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]

跟踪边界的算法很简单。从左上角的方块开始。如果当前方格有复选标记，则向右转。否则，下去。我希望您能了解这个过程如何在时间上访问每列中的第一个复选标记。这是另一张可能的桌子。

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

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