最长有效括号

爱疯

wanghan519 发表于 2024-1-8 11:05
从前向后好像找不到这个
()((()())
从后向前找不到这个

谢谢 wanghan519！



   如果 s 本身是有效括号串，只需单向遍历。
   ...............无......，必须双向遍历。比如 s = "(()"



是我不仔细，举个类似的更简单的例子。
想到该方法的人，当初是咋想出来的噢。。。。

爱疯

小结



1）最长连续子串的题目，想到用滑动窗口很正常吧。
   滑动窗口的本质：一旦条件不再符合，便滑动。
   对于本题，一旦子串不再是有效括号，便滑动。

   怎么知道是不是有效？有多余的括号，并且在错误位置上，则是无效。
   怎么知道有没有多余？计数。

   比如从左往右遍历，
       如果 左 > 右 ，有机会凑成有效括号，继续尝试。
       如果 左 = 右 ，当前已............，更新。
       如果 左 < 右 ，没机会............，有多余的右括号，并且在错误位置上。清零为下一个窗口重新计数。
   同理从右往左遍历。

   滑动窗口一般修改的是窗口的左右边界，
   窗口尺寸 = 窗口右边界 - 窗口左边界 + 1

   因为利用有效括号特性，左右括号的计数相等，所以修改的是窗口中元素的计数，
   窗口尺寸 = 括号计数 * 2

   从运行结果上可验证，
   如果主串是有效括号，只需单向遍历。因为没多余的括号，所以从哪个方向遍历都一样。
   ..........无......，必须双向遍历。因为有多余的括号，并且在错误位置上，所以取两个返回值中的更大那个。
                                     比如 s = "(()"，正向遍历不能检测到返回0，反向能检测到返回2。