题目描述

给你一个只包含 '('')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例

输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
输入:s = ""
输出:0

题解

  1. 维护一个栈,栈底存放最后一个不合法的右括号
  2. 遇到左括号进行入栈
  3. 遇到右括号弹栈
    1. 如果此时栈为空,说明当前右括号不合法,因此,将当前右括号下标入栈
    2. 栈不为空,说明该右括号合法,只需要计算长度即可
  4. 每次计算,统计最大值

Coding

class Solution {
public int longestValidParentheses(String s) {
if(s == null || s == ""){
return 0;
}
int len = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
char[] arr = s.toCharArray();
for(int i = 0;i < arr.length;i++){
char c = arr[i];
if(c == '('){
stack.push(i);
}else{
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}else{
len = Math.max(len,i - stack.peek());
}
}
}
return len;
}
}