algorithm - 最长的非递减序列-n log n？

我在试着理解n logn解。似乎您不必在任何给定点存储整个临时列表，只需最后一个元素即可。
这是怎么回事？
我不想张贴现有的帖子，所以创建了一个新的帖子。
花了很多时间去理解它.：。（

最佳答案

您不必在任何给定点存储整个临时列表，只需最后一个元素即可。
首先，回想一下o（n2）解决方案：设置一个数组L，该数组在每个元素i处具有结束于元素A的最长非递减子序列的长度。下面是一个例子：

A: 2 5 7 3 8 2 9 6 9
L: 1 2 3 2 4 2 5 3 6

现在想象一下设置一个数组i，它在每个索引M处存储k的元素，该元素结束长度A的最长非递减子序列。下面是k如何看待每个步骤（破折号M显示未填写的位置）

M (step 0) - - - - - - - - -
M (step 1) 2 - - - - - - - -
M (step 2) 2 5 - - - - - - -
M (step 3) 2 5 7 - - - - - -
M (step 4) 2 3 7 - - - - - -
M (step 5) 2 3 7 8 - - - - -
M (step 6) 2 2 7 8 - - - - -
M (step 7) 2 2 7 8 9 - - - -
M (step 8) 2 2 6 8 9 - - - -
M (step 9) 2 2 6 8 9 9 - - -

手动完成示例以了解填充数组的机制。
接下来是关键的观察：在每个步骤中，-都是按非递减顺序排列的。直观地说，这是清楚的，因为否则，较大的数字可以附加到较长的序列，并向上移动数组M。
这允许您构造算法：
存储已填写的M的最后一个位置
当您到达M时，在maxPos中运行二进制搜索以查找应该放置M的位置
如果最终位于数组的中间，请将旧值替换为A[i]
如果元素大于或等于迄今为止添加到M[0..maxPos]的所有元素，则将A[i]添加到末尾，并递增min(A[i], oldValue)
很容易看出上面的算法是o（n*log（n）），因为它的每个M步骤都使用一个二进制搜索，即log（n）。