我得到一个看起来像这样的字符串：
1011010100
我的任务是找到一个子字符串的长度，其中空值的数量总是<=个数。这应该总是在从右到左和从左到右“扫描”子字符串时发生。所以在这个例子中，答案是：
10110101 => 8
我知道复杂度应该是 O(n) 或 O(n log n)，因为长度可以达到 10^6
有任何想法吗？
问问题
532 次
3 回答
1
O(n)解决方案实际上非常简单，通过构建“高度数组”，表示 1 相对于 0 的数量。所以高度为 2 意味着 1 比 0 多 2 个。一旦在某些条件下执行一些极大值检查，我们就会遍历高度数组。
关键观察
请注意，满足条件的子数组的高度必须在开始时最小，在结束时最大（相对于子数组，而不是整个数组）。
问题中样本的高度数组可以这样绘制，并带有标记的答案：
v /\/\/\ /\/ \ ^
证明：
假设开始时高度不是最小值，这意味着子数组内部有一个点高度低于开始。此时，0的个数应该大于1的个数。矛盾。
假设最后的高度不是最大值，这意味着子数组中有一个点的高度大于结尾，比如在 index 处j。然后在 indexj到末尾有 0 多于 1 （因为高度减小），所以当我们从右到左“扫描”子数组时，我们会发现 index 处的 0 多于 1 j。矛盾。
算法
现在问题可以解释为找到最长的子数组，它以子数组中的最高高度结束，同时保持最小值不超过开始时的高度。这与 klrmlr 提到的最大子数组问题非常相似（“数组的连续子序列”更好地称为“子数组”）。这个想法不是保持一个O(n)状态，而是保持“迄今为止的最大值”和“此时的最大值”。
遵循该算法，下面是伪代码，遍历数组一次：
过程 Balance_Left_Right
- 记录迄今为止的最低点和最高点
- 如果此时的高度低于目前为止的最低点，则将起点改为该点之后的索引
- 如果此时的高度高于或等于迄今为止的最高点，那么这是一个有效的子数组，记录长度（以及开始和结束索引，如果你喜欢）
然而，我们很快就会看到这个测试用例的问题（正如 Adam Jackson 通过个人交流指出的那样）：，1100101可视化如下：
/\ / \/\/
正确答案是 3（最后 101 个），但上面的算法会得到 2（前 11 个）。这是因为我们的答案显然隐藏在一座“高山”后面（即答案的最低点不低于山，而答案的最高点不高于山）。
因此，我们需要确保在运行过程 Balance_Left_Right（上图）时，没有隐藏答案的“高山”。因此解决方案是从右侧遍历数组一次，尝试将数组划分为多个部分，在每个部分中，此属性保持：“1 的数量始终 >= 0 的数量，从右侧遍历"，而且对于每个部分，它不能再向左扩展。
然后，在每个部分中，当从左侧遍历时，将在该部分的末尾具有最大高度，这就是最大值。并且可以证明，有了这个属性， balance_left_right 方法就可以找到本节的正确答案。因此，我们只需在每个部分上调用 balance_left_right 方法，然后从中取最大答案。
现在，您可能会问，为什么在每个部分上运行 Balance_Left_Right 就足够了？这是因为答案要求属性从左侧和右侧保持，因此它必须位于其中一个部分内，因为每个部分都满足一半的属性。
该算法仍然是O(n)因为我们只访问每个元素两次，一次从右侧，一次从左侧。
最后一个测试用例将被划分如下：
/|\ | / | \|/\/ ** ***
其中仅使用标有星号 (*) 的部分。
所以新算法如下：
过程 Max_Balance_Left_Right
- 从右边开始对输入进行分区，其中 1 >= 0 的数量（使用右边的 Balance_Left，或者可以称之为 Balance_right）
- 在每个分区上运行 Balance_Left_Right
- 取最大值
这是Python中的代码：
def balance_left_right(arr):
lower = 0
upper = -2**32
lower_idx = 0 # Optional
upper_idx = -1 # Optional
result = (0,0,0)
height = 0
length = 0
for idx, num in enumerate(arr):
length += 1
height += 1 if num==1 else -1
if height<lower:
lower = height # Reset the lowest
upper = height # Reset the highest
lower_idx = idx+1 # Optional, record the starting point
length = 0 # Reset the answer
if height>=upper:
upper = height
upper_idx = idx # Optional, record the end point
if length > result[0]: # Take maximum length
result = (length, lower_idx, upper_idx)
return result
def max_balance_left_right(arr):
all_partitions = []
start = 0
end = len(arr)
right_partitions = balance_left(reversed(arr[start:end]))
for right_start, right_end in right_partitions:
all_partitions.append((end-right_end, end-right_start))
result = (0,0,0)
for start, end in all_partitions:
candidate = balance_left_right(arr[start:end])
if result[0] < candidate[0]:
result = (candidate[0], candidate[1]+start, candidate[2]+start)
return result
def balance_left(arr):
lower = 0
start_idx = 0
end_idx = -1
height = 0
result = []
for idx, num in enumerate(arr):
height += 1 if num==1 else -1
if height < lower:
if end_idx != -1:
result.append((start_idx,end_idx))
lower = height
start_idx = idx+1
end_idx = -1
else:
end_idx = idx+1
if end_idx != -1:
result.append((start_idx, end_idx))
return result
test_cases = [
[1,0,1,1,0,1,0,1,0,0],
[0,0,1,0,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0,1],
[1,1,1,0,0,0,1,0,0,1,1,0,1,1,0,1,1,0],
[1,1,0,0,1,0,1,0,1,1,0,0,1,0,0],
[1,1,0,0,1,0,1],
[1,1,1,1,1,0,0,0,1,0,1,0,1,1,0,0,1,0,0,1,0,1,1]
]
for test_case in test_cases:
print 'Balance left right:'
print test_case
print balance_left_right(test_case)
print 'Max balance left right:'
print test_case
print max_balance_left_right(test_case)
print
这将打印：
左右平衡： [1, 0, 1, 1, 0, 1, 0, 1, 0, 0] (8, 0, 7) 左右最大平衡： [1, 0, 1, 1, 0, 1, 0, 1, 0, 0] (8, 0, 7) 左右平衡： [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1] (6, 12, 17) 左右最大平衡： [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1] (6, 12, 17) 左右平衡： [1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0] (8, 9, 16) 左右最大平衡： [1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0] (8, 9, 16) 左右平衡： [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0] (10, 0, 9) 左右最大平衡： [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0] (10, 0, 9) 左右平衡： [1, 1, 0, 0, 1, 0, 1] (2, 0, 1) 左右最大平衡： [1, 1, 0, 0, 1, 0, 1] (3, 4, 6) 左右平衡： [1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1] (5, 0, 4) 左右最大平衡： [1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1] (6, 8, 13)
为了您的眼睛享受，测试用例的高度数组：
第一的：
v
/\/\/\
/\/ \
^
第二：
\
\/\/\ v
\/\/\ /\/\/\
\/ \/
^
第三：
v
/\ /\
/ \ /\/
/ \/\ /\/
\/
^
第四：
v
/\ /\
/ \/\/\/ \/\
^ \
第五：
/\ v
/ \/\/
^
第六：
/\ v
/ \ /\
/ \/\/\/ \/\ /
/ ^ \/\/
/
关于问题的说明
由于一些读者对OP到底想要什么感到困惑，尽管问题中已经明确说明了，让我通过一些例子来解释这个问题。
首先，来自问题的任务：
我的任务是找到一个子字符串的长度，其中空值的数量总是<=个数。这应该总是发生在从右到左和从左到右“扫描”子字符串时
这指的是“加泰罗尼亚号码投票问题”或“可用更改问题”。在 Wiki 中，您可以检查“单调路径”问题，您可以将“向右移动”映射为“1”，将“向上移动”映射为“0”。
问题是找到原始数组的子数组，这样，当从左到右和从右到左遍历子数组时，这个属性成立：
到目前为止看到的 0 的数量不应超过迄今为止看到的 1 的数量。
例如，字符串1010包含从左到右的属性，因为如果我们从左到右扫描数组，总是会有比 0 多的 1。但是该属性从右到左不成立，因为从右边遇到的第一个字符是 0，所以一开始我们有更多的 0（有一个）而不是 1（没有）。
例如 OP 给出的例子，我们看到字符串的答案1011010100是前八个字符，即：10110101. 为什么？
好的，所以当我们从左到右遍历子数组时，我们看到 1 总是比 0 多。让我们在从左到右遍历数组时检查 1 和 0 的数量：
1：数（0）= 0，数（1）= 1 0：数（0）= 1，数（1）= 1 1：数（0）= 1，数（1）= 2 1：数（0）= 1，数（1）= 3 0：数（0）= 2，数（1）= 3 1：数（0）= 2，数（1）= 4 0：数（0）= 3，数（1）= 4 1：数（0）= 3，数（1）= 5
我们可以看到，在任何时候，0 的数量总是小于或等于 1 的数量。这就是该属性从左到右的原因。同样的检查可以从右到左进行。
那么为什么不1011010100回答呢？
让我们看看我们何时从右到左遍历字符串：
0：数（0）= 1，数（1）= 0 0：数（0）= 2，数（1）= 0 1：数（0）= 2，数（1）= 1 ...
我没有进行完整遍历，因为从第一步开始就已经违反了该属性，因为我们有num(0) > num(1). 这就是字符串1011010100不满足问题约束的原因。
您还可以看到，我的“高度数组”实际上是 1 的数量和 0 的数量之间的差异，即：num(1) - num(0)。因此，为了拥有该属性，我们必须将 [相对] 高度设为正数。这可以通过使高度不小于初始高度来可视化。
于 2013-10-21T02:26:53.680 回答
1
这是我的算法：
从右侧开始：
1. if you find 0 increment the value of count
2. if you find 1 decrement the count
将这些值存储在一个数组中，即v[]. 例如
a[] = {1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1}
v[] = {0, 1, 0,-1, 0, 1, 0, 1, 2, 1, 2, 1, 0, -1}
现在问题减少到从Viei, j中查找索引v[i] < v[j]和i<j。
证明：
如果您在这里看到i=0并且j=11是可能的答案并且值为v[i]=0, v[j]=1。这意味着直到j 我们0在字符串中有一个额外的并且v[i]=0这意味着从i to j窗口大小来看，0通过放置 extra 来取消额外的1。因此得到了答案。
希望能帮助到你。如果您有疑问，请告诉我。谢谢。
于 2013-10-21T00:04:08.623 回答
0
（几乎正确，即轻微错误）线性时间解
对问题进行了两次重新编码（稍后删除了一个......）和一个滑动窗口。
编码 A
您可以压缩输入以产生后续零或一的数量：
+1 -1 +2 -1 +1 -1 +1 -2
这会产生编码 A并且需要 O(n) 时间。
编码 B
现在，在编码 A 中，每当遇到两个连续数字的总和 > 0 时，都会进一步压缩。在编码 B中，括号中的数字表示子字符串的长度：
+2(4) -1 +1 -1 +1 -2 ==> +2(6) -1 +1 -2 ==> +2(8) -2
这也需要 O(n)。在这里，我们立即得到了解决方案：长度为 8 的字符串，其中 1 比 0 多两个。让我们尝试一个更复杂的实例（在编码 A 中给出）：
+5 -8 +4
在这里，对编码 B 的转换没有帮助：
+5(5) -8 +4(4)
还要考虑以下实例（编码 B）：
+5(9) -6 +4(4) -6 +5(7) -6 +4(6) -6 +5(9)
该序列将用于演示...
滑动窗口
首先，确定从左边开始的最佳解决方案：
+5 -6 +4 -6 +5 > 0 ==> 9+6+4+6+7=32
现在，扩展它以找到从第三个位置 (+4(4)) 开始的最佳解决方案：
+4 -6 +5 -6 +4 > 0 ==> 4+6+7+6+6=29
这个解决方案并不比我们发现的第一个更好。继续前行：
+5 -6 +4 -6 +5 > 0 ==> 7+6+6+6+9=34
这是最好的解决方案。该算法可以在 O(n) 中实现，因为头和尾只向前移动。
上面的简短描述并未涵盖所有细节（编码 B 左侧的负数，头尾相接，...）。此外，也许不需要重新编码，滑动窗口可以直接在 0-1 表示上实现。但是，我只有在重新编码后才能完全理解这个问题。
摆脱编码 B
实际上，正如 Millie Smith 善意地指出的那样，“编码 B”可能是有损的，这意味着它可能会在某些（尚未确定的）极端情况下导致较差的解决方案。但是滑动窗口算法在编码 A 上同样有效，所以甚至可能需要跳过对编码 B 的转换。（懒得重写算法的解释......）
于 2013-10-20T19:07:21.117 回答