前言:记录下自己的思考过程以供后续回看,如果恰巧能够帮到你,不胜荣幸。
在LeetCode上面看到了正反两次遍历的做法,感到很神奇,但是又不知道为什么是对的。于是认真的想了想,总结如下:
本题解着重讨论其他题解中两趟扫描方法的正确性。具体思路可以参考其他题解,这里不再赘述。
我们记左括号数量为l,右括号数量为r
思考一:当我们在遍历时,我们在遍历哪个区间?
由y总的视频讲解可知,整个区间是可以分段的。即,若当前区间的)
数量大于(
数量(从左至右遍历),
则标志着本段结束,开启下一个段,并且段之间永远不会存在合法区间
。这里的证明可以看y总的视频讲解。
经过观察可以发现,我们每一次更新下一段时,将l, r
清0,实际上是将区间左端点更新到下一段的开头。所以,我们的区间为以当前合法段的开端为区间左端点,可以向右延伸的最长合法位置
(合法是指不被丢弃,不一定是答案)。
思考二:当不出现特殊情况时,我们可以得到最长长度吗?
这个问题等价于,是否存在一个合法区间,不从本段起始点开始,并且长度大于答案。如下图
其实这种区间是不存在的。原因如下:
当分段发生时,如下图。此处即为非法位置,有r > l
,且当前位置为)
。因为是一旦发生非法就立即分段,所以有r = l + 1
,那么他的前序位置一定满足r == l
。这不就是我们想要的答案区间吗?而且这个值一定是本段最大的。
思考三:特殊情况是如何出现的?
由上一个思考可知,我们无法得出最大长度,是因为本段的最后一个状态为l > r
,那么我们就不能推出前序位置的状态
了。
但是我们仍然有其他性质可以利用,观察到本段最后一个位置满足l > r
。那么我们一定可以得出:本段一定为整个字符串的最后一段,即结尾!
我们可以使用反证法。如果后续还存在字符的话,那么不论该字符是(
还是)
,下一个位置一定满足l >= r
,仍然是合法的。那么我们就不会在这个位置分段了。
所以理论上我们只需要反向遍历最后一段就可以了。
思考四:那么为什么反向遍历可以得出这一段的最大长度呢?
由上一个思考可知,最后位置满足l > r
。即整个段的(
数大于)
数。而对于反向遍历来说,这种状态是非法的!因为反向遍历要求r >= l
。所以反向遍历对这一段的分段一定发生在左端点以右(包括左端点)的某个位置。而这个位置就可以算出最后一段的最大长度。
最后:很感谢你能看完我啰嗦这么一大堆QAQ。
例行公事贴个代码8。
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int l = 0, r = 0;
int res = 0;
for(int i = 0; i < n; i ++) {
if(s[i] == '(') l++;
else r++;
if(r > l) l = r = 0;
else if(r == l) res = max(res, 2 * r);
}
l = r = 0;
for(int i = n - 1; i >= 0; i --) {
if(s[i] == '(') l++;
else r++;
if(l > r) l = r = 0;
else if(r == l) res = max(res, 2 * r);
}
return res;
}
};