最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
思路分析
错误思路规避
刚看到括号对, 第一反应就是栈操作的括号匹配, 认为只要匹配到匹配失败的时候记录这条括号串的长度, 在遍历完整个串之后, 通过最大值筛选就获得了最长有效括号长度. 然而事实证明困难题没有那么憨憨 对于"( ) ( ( )"显然简单的匹配栈会把这个长度定为4,实际上只有2 ##### 问题出在哪呢? ( ) ((((((((( ( ) 在两个正常括号中间的压栈操作不会终止长度的累积 当然也不能粗暴的终止,毕竟也有( ) ( ( ( ( ) ) ) ) ) 的情况
改良方法
参考了题解大神的思路之后, 明白了单纯压char型 ' ( '入栈是一种很憨憨的行为...... 同样是压栈匹配, 人家压的下标.....消耗一样,却额外带来了位置信息
匹配时括号对会产生一个位置差, 而对于这个差内部肯定是合法的括号串. ( ~~~~~~~) 假如是非法串, 要么是 ( 多了,那匹配时会匹配内部多的 ( ,而不是外部那个. 要么是 ) 多了, 那肯定已经把栈清空了, 外围也不会有匹配括号.
每次匹配成功会通过位置差得到一个当前长度信息length=i-stack.top()
注意这里的top是已经匹配pop出一个(
之后,再取的top,此时的top为目前合法字符串的开始位置的前一个
假如top和pop为同一个,对于 ((())) 的嵌套形式是没问题的, 但对于连串形式如:
例如 ( ( ) ( ) ( ) ( ) ( ) ) )
string[9]和string[10]匹配了,目前合法长度肯定不是10-9=1...实际上是10-0=10
也因为这个i-top的方法,我们需要在最开始的栈底压入一个-1, 代表字符串开头 针对 ( ) ( ) ( ) 的情况, 最后一个右括号pop完, 不压入一个-1你让人家减谁去算长度....
顺带一提原方法错误的案例 再看( ) ( ( ), 原方法因为是只要不匹配失败, 每过一位都会长度++,因此产生错误结果 4 而利用位置信息差算长度的方法, 只会算出两个长度为2 的括号对 ,最大也就是2.
题解代码
算法比较简单, 但分析细节还是比较令人舒适的~ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
public:
int longestValidParentheses(string s)
{
int result=0;
int i=0;
stack<int left;
left.push(-1);//压入字符串头，以防（）（）（）（）情况
while(i<s.size())
{
if(s[i]=='(') //左括号 下标 入栈
left.push(i);
else //右括号消除一个左括号，并用下标差计算长度
{
left.pop();
if(left.empty()!=true)
{
if(i-left.top()result)
result=i-left.top();
}
else
left.push(i);
}
i++;
}
return result;
}
};