最长有效括号
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
方法一、栈
由于要存在配对，必然有')'存在，配对的长度为上一个')'到当前')'之间的距离，即为最长配对子串，因此，我们使用栈结构，存储上一次配对的')'所在的索引。栈存放**[最后一个没有被匹配的右括号的下标]**
复杂度分析
时间复杂度：O(n)，n为字符串的长度，遍历一次
空间复杂度：O(n)，n为字符串的长度，栈最多存储n个字符
Swift
func longestValidParentheses(_ s: String) -> Int {
let cnt = s.count
var res:Int = 0
//栈，存放[最后一个没有被匹配的右括号的下标]
let stack = Stack<Int>()
stack.push(-1)//为了统一期间，假数据填充
for i in 0..<cnt {
let chara = s[s.index(s.startIndex, offsetBy: i)]
if chara == "(" {
stack.push(i)
}else if(chara == ")") {
let _ = stack.pop()
if stack.count() == 0 {
stack.push(i)
}else {
res = max(res, i - (stack.top() ?? 0))
}
}
}
return res
}
OC
- (NSInteger)longestValidParentheses:(NSString *)s {
NSInteger res = 0;
//存放[最后一个没有被匹配的右括号的下标]
StackOC *stack = [[StackOC alloc] init];
[stack push:@(-1)];//
for (NSInteger i=0; i<s.length; i++) {
unichar character = [s characterAtIndex:i];
if (character == '(') {
[stack push:@(i)];
}else if(character == ')') {
[stack pop];
if ([stack empty]) {
[stack push:@(i)];
}else {
//当前右括号索引减去上一个右括号的索引，表示最长串
res = MAX(res, i-[[stack top] integerValue]);
}
}
}
return res;
}
方法二、双指针+双向遍历
思想：left对应 '('个数，right对应')'个数，当两者相等时，说明配对成功。
边界处理：当从左向右遍历时，right>left表示不连续了，要从0开始计数，因此将left和right置为0。
当从右向左遍历时，当left>right时表示不连续了，计数归0
复杂度分析
时间复杂度：O(n)，n为字符串的长度，遍历一次
空间复杂度：O(1)
Swift
//双指针法，空间复杂度为O(1)
func longestValidParentheses(_ s: String) -> Int {
let cnt = s.count
var left = 0, right = 0, maxLen = 0
//从左向右找一次
for i in 0..<cnt {
let str = s[s.index(s.startIndex, offsetBy: i)]
if str == "(" {
left += 1
}else if(str == ")") {
right += 1
}
if left == right {
maxLen = max(maxLen, 2*right)
}else if(right > left) {
left = 0
right = 0
}
}
//从右向左找一次
left = 0; right = 0
var j = cnt - 1
while j > 0 {
let str = s[s.index(s.startIndex, offsetBy: j)]
if str == "(" {
left += 1
}else if(str == ")") {
right += 1
}
if left == right {
maxLen = max(maxLen, 2*right)
}else if(left > right) {
left = 0
right = 0
}
j -= 1
}
return maxLen
}
OC
//双指针+左右遍历
- (NSInteger)longestValidParentheses:(NSString *)s {
NSInteger left = 0, right = 0, maxLen = 0;
//从左向右匹配一次
for (NSInteger i=0; i<s.length; i++) {
unichar charater = [s characterAtIndex:i];
if (charater == '(') {
left++;
}else if(charater == ')') {
right++;
}
if (left == right) {
maxLen = MAX(maxLen, 2 * right);
}else if(right > left) {
left = right = 0;
}
}
//从右向左匹配一次
for (NSInteger i=s.length-1; i>0; i--) {
unichar charater = [s characterAtIndex:i];
if (charater == '(') {
left++;
}else if(charater == ')') {
right++;
}
if (left == right) {
maxLen = MAX(maxLen, 2*left);
}else if(left > right) {
left = right = 0;
}
}
return maxLen;
}
