什么是最小缓冲区值,使得一组int将按递增顺序排序？

Question

问题:给定一个整数数组,找到最小缓冲区值,以便可以按严格递增的顺序对数组进行排序.数组中的每个元素都可以加上或减去缓冲区值.

Ex: [4, 0, 9, -2]

最小缓冲区值为6,因为您可以将数组更改为:

[4 - (6 or 5 or 4 or 3), 0 + (-1 or 0 or 1 or 2), 9 - (6) = 3, -2 + (6) = 4]

我相信我有一个解决方案可以使用O(N ^ 2),但我想知道我是否可以做得更好.

编辑:没关系,我的解决方案不起作用.

我的解决方案

对于每个元素,绘制一条斜率为1的线,通过该元素.找到允许每个元素移动到线上的最小缓冲区值.跟踪获得的缓冲区值,并在最后返回最小的缓冲区值.

谢谢

Answer 1

O(n)可以通过逐一循环数组并保持不变式正确并跟踪当前缓冲区大小来实现：

我们从左边开始，一一向右走
根据定义，单个元素子数组是排序的
使用当前缓冲区将当前元素调整为尽可能低的值（因此不变式仍然成立）
如果当前元素（调整后）比前一个元素大，那么我们不需要做任何事情（排序）
否则（未排序）我们需要更新缓冲区（增加它） - 这是通过检查当前元素和已排序数组的最大值（只是前一个元素）之间的差异来轻松完成的（因此我们添加到abs((curr-prev)/2) + 1当前缓冲区）以及先前/当前值（尽可能的最小值）。此时，我们不需要关心较早的条目，因为由于我们正在增加缓冲区以减少先前/当前的值，因此我们可以简单地abs((curr-prev)/2) + 1从每个先前的值中减去，并且不变量将保持不变。

一些示例可以使其更加清晰（粗体 - 当前，斜体 - 先前）：

一）输入：[4,0,9,-2]

[ 4 ] - 按定义排序
[ 4 , 0 ] - 未排序，用缓冲区更新当前缓冲区 [ 4 , 0 ], diff = (4-0)/2+1 = 3 => [1,2], buffer = 3 // 更新完成如下遵循：将前一个值减少整个 diff，对于当前值，检查 newPrevious（此处为 1）加 1 是否在 current+-diff 范围内，如果是，则设置 newPrevious+1，否则设置 current+diff
[1, 2 , 9 ] - 已排序，用缓冲区更新当前的 [1, 2 , 6 ] // 这里更新的完成方式与之前的更新类似，但我们不执行 current+diff，而是执行 current-diff
[1,2, 6 , -2 ] - 未排序，用缓冲区 [1,2, 6 , 1 ] 更新当前缓冲区，仍然未排序，所以 diff = (6-1)/2+1 = 3, buffer = 6, [ 1,2,3,4 ]

完成，缓冲区 = 6

II) 输入：[40, 31, 140, 131]

完成，缓冲区 = 5

III) 输入：[1,1,1,1]

完成，缓冲区 = 2

IV) 输入：[7,11,1,2,3]

[ 7 ] - 按定义排序
[ 7 , 11 ] - 排序，调整 [7,11]
[7, 11 , 1 ] - 未排序，调整 [7,11,1]，diff = (11-1)/2+1 = 6 => [7,5,6]，buffer = 6
- 在这里我们可以看到，我们不需要检查 11 之前的任何内容，因为所有前面的数字都小于 11，所以如果我们执行 11 - X 我们可以简单地执行 PREVIOUS - X 并且不变量仍然成立
[ 7,5,6,2 ] - 未排序，调整 [7,5,6,7] <- 不变式仍然成立，我只是没有在上一步中调整前 7 个
[7,5,6, 7 , 3 ] - 未排序，调整 [7,5,6,7,8]

完成，缓冲区 = 6

五）输入：[0,1,3,-15]

直到 [0,1,3] 没有任何改变

[0,1, 3 , -15 ] diff = 10，调整上一个和当前的 [0,1,-7,-6] - 在这里我们再次可以看到我们将缓冲区从 0 增加到 10，因此所有数字都在左边3 和 3 本身可以减 10，并且不变量将保持不变，但对于算法的其余部分，我们不需要这样做

完成，缓冲区 = 10

六）输入：[1,2,3,4]

完成，缓冲区 = 0