我给了一个看起来像这样的字符串:
1011010100
我的任务是找到一个子串的长度,其中空值的数量总是<= 1的数量.这应该始终在从右到左和从左到右'扫描'子串时发生.所以在这个例子中,答案是:
10110101 => 8
我知道复杂性应该是O(n)或O(n log n),因为长度可以达到10 ^ 6
有任何想法吗？
解决方案O(n)实际上很简单，通过构建“高度数组”来表示 1 的数量相对于 0 的数量。所以高度为 2 意味着 1 比 0 多 2 个。一旦在某些条件下执行了一些最大值检查，我们就会迭代高度数组。
关键观察
请注意，满足条件的子数组必须在开头具有最小高度，在末尾具有最大高度（相对于子数组，而不是整个数组）。
问题中样本的高度数组可以像这样绘制，并带有标记的答案：
v /\/\/\ /\/\ ^
证明：
假设开始时高度不是最小的，这意味着子数组内有一个点的高度低于开始处。此时0的个数应该大于1的个数。矛盾。
假设末端的高度不是最大，这意味着子数组中有一个点的高度大于末端，例如在索引处j。然后在索引j到末尾处，0 比 1 多（因为高度减小），因此当我们从右向左“扫描”子数组时，我们会发现在索引 处 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
这是 Python 中的代码：
v
/\/\/\
/\/ \
^
这将打印：
左右平衡： [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到底想要什么感到困惑，尽管问题中已经明确说明了这一点，让我通过一些例子来解释这个问题。
首先，问题中的任务：
我的任务是找到一个子字符串的长度，其中空值的数量始终<= 1 的数量。从右到左和从左到右“扫描”子字符串时应该总是发生这种情况
这指的是“加泰罗尼亚号码选票问题”或“可用找零问题”之类的问题。在 Wiki 中你可以检查“单调路径”问题，其中你可以将“向右移动”映射为“1”，“向上移动”映射为“0”。
问题是找到原始数组的一个子数组，这样，当从左到右和从右到左遍历子数组时，这个属性成立：
到目前为止看到的 0 的数量不应超过目前看到的 1 的数量。
例如，字符串保存从左到右的1010属性，因为如果我们从左到右扫描数组，则 1 的数量总是多于 0 的数量。但该属性从右到左不成立，因为从右侧遇到的第一个字符是 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)。因此，为了拥有该属性，我们必须使[相对]高度为正。这可以通过高度不小于初始高度来可视化。