在leetcode面经上发现一道有意思的题目，大家可以一起讨论一下

内容是这样的：
Given a 1-d array candy crush, return the shortest array after removing all the continuous same numbers (the repeating number >= 3)
input: 1-d array [1, 3, 3, 3, 2, 2, 2, 3, 1]
return: [1, 1]
Time complexity should be better than O(n^2)
Mod edit: To slow down the posting of O(n^2) and O(n) "correct" solutions, here is another testcase:
[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should return [3,1,3,2,3]
我想了很久只能想出暴力的dfs尝试每一个可能，但是根据出题人这道题可以优于O(n^2)不知道是说出来坑人的还是真有更优的解法

说 O(n) 的都是胡 JB 扯, 这题只能 DFS, On2 都不行

这个问题可以用两阶段的动态规划做吧，时间是O(n^3)，不知道可不可以进一步优化了

--
首先我们定义一个数组A可以被“全消除”，记作 IsFullyCrushable(A)，当且仅当存在一个消除过程，使得A中的所有元素最后都被消除掉。

然后，给定输入数组S，定义可以全消除的区间集合：I = { [i, j] | IsFullyCrushable( S[i..j] ) }

也就是说I是S中可以被全消除的所有子串的区间集合，易知I中的区间数量不超过 n^2

举个例子，对于 S = 322233322，可以被全消除的子串有：
(1) 区间 [1, 3]: .222.....
(2) 区间 [4, 6]: ....333..
(3) 区间 [0, 5]: 322233...
(4) 区间 [0, 6]: 3222333..
(5) 区间 [1, 6]: .222333..
(6) 区间 [1, 7]: .2223332.
(7) 区间 [1, 8]: .22233322
(8) 区间 [2, 8]: ..2233322
(9) 区间 [3, 8]: ...233322

那么对应的 I 就是上面9个区间的集合。

然后我们有如下关键性质：

定理(a)：给定数组S，通过一系列消除过程可以消除的最大长度K，等于I中互不相交的区间子集的最大总长度

还是上面的例子，那么最大的互不相交区间集合总长度是K = 8（这个例子里最优解只有一个元素[1, 8]，但是把输入弄复杂一点的话最优解就会是多个区间组成的集合了）

然后原题要计算的是最短剩余长度，那么返回 len(S) - K 即可。


所以接下来需要进一步回答三个问题：
--
1. 定理(a)如何证明？

定理(a)本身可以通过考察消除过程来证明，这里略过..

--
2. 给定I，如何求I中互不相交区间子集的最大总长度？

本质上是一个weighted interval scheduling problem，可以先排序，再DP，参考这里：https://courses.cs.washington.ed ... ides/06dp-sched.pdf

时间复杂度由排序时间决定，因为I中元素数量不超过n^2，所以就是 O(n^2 * log(n))

--
3. 如何计算得到集合 I ？

为了简洁，记 C(i, j) = IsFullyCrushable( S[i..j] )，那么对于所有区间[i, j]，计算C(i, j)并将值为"true"的区间加入I即可。

现在我们要写出C(i, j)的状态转移方程，那么就是C(i, j)值为true，当且仅当下面任一条件被满足：
(1) S[i..j]全部为同一字符且长度大于等于3
(2) 存在i < k < j，使得 C(i, k)为true 且 C(k + 1, j)为true
(3) 存在i < m < n < j，使得C(m, n)为true 且 S[i..m-1]并上S[n+1,j]全部为同一字符且长度大于等于3

这个状态转移方程的时间复杂度主要在(2)需要枚举所有k，综合起来就是 O(n^3)

注意到对于(3)式我们不需要枚举所有m，n，只要同时从左从右贪最多的同一字符然后检查即可，其正确性可以用数学归纳法证明


补充内容 (2019-6-16 03:09):
谢谢zjck1995指出来计算I时没有考虑到 5 1 1 1 5 1 1 1 5 这种情况，处理方法可以引入一个新函数H(i, j)表示消除后可以得到的最多"i位置上的字符"个数，然后式子(3)改为 H(i, j) >= 3，具体可以看下面帖子的讨论

补充内容 (2019-6-16 14:34):
写了一份参考代码：http://cpp.sh/3jcqk

FYI:  https://codeforces.com/blog/entry/67618

我连 O(N^2) 都想不出来...

瞄了一眼，感觉用一个sliding window size of 3，线性时间可以解。dequeue或者手工模拟都行吧

把这个array，建成double linked list，可以在O(n)做完

Frango 发表于 2019/06/14 21:29:08
瞄了一眼，感觉用一个sliding window size of 3，线性时间可以解。dequeue或者手工模拟都行吧

大于三的连接也要消除啊

zxcvbn3018 发表于 2019/06/14 22:53:17


大于三的连接也要消除啊

早上急着考试没表达清楚。
如果dq空或者当前字母和dp末字母相同，当前字母push到dq末尾.
否则，如果dq大小大于等于3，消除dq内所有字母,poll all，新字母入dq.如果dq大小小于3,保留所有dq字母poll all，新字母入dq

Frango 发表于 2019-6-14 09:43
早上急着考试没表达清楚。
如果dq空或者当前字母和dp末字母相同，当前字母push到dq末尾.
否则，如果dq大 ...

2223332 最后一个2你准备怎么办

[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] 怎么判断消掉的顺序？比如这个case是先消除index为2的三个2，还是index为5的三个1？顺序会影响输出的结果

Use stack could solve this problem in linear time. The result should store in the stack finally, we may need another stack to store the current continue elements in the stack.