一、题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
二、思路分析
本题可以采用栈的方法解决，创建一个 leftStart 变量来表示指向合法括号的最左边的索引位置，用 result 记录最长有效（格式正确且连续）括号子串的长度。
三、代码参考
1、Java
class Solution {
public int longestValidParentheses(String s) {
// 创建栈空间
Stack<Integer> stack = new Stack<>();
// result 记录最长有效（格式正确且连续）括号子串的长度
int result = 0;
// 设置变量 leftStart 表示合法括号序列的起始索引位置，指向一个左括号，初始值为 0
int leftStart = 0 ;
// 循环遍历字符串数组
for(int i = 0; i < s.length(); i++){
// 访问左括号时，把它存储到栈里
if(s.charAt(i) == '('){
stack.push(i);
}
// 访问右括号时
else{
// 如果当前栈为空，说明这个右括号在前面没有和它匹配的左括号，那么 leftStart 需要发生改变
if(stack.isEmpty()){
// 索引变为当前字符的下一个
leftStart = i + 1;
}else{
// 移除栈顶元素
stack.pop();
// 如果此时栈为空，说明当前右括号为右端点的合法括号序列的左端点为 leftStart，则更新长度 i - leftStart + 1
if(stack.isEmpty()){
result = Math.max(result, i - leftStart + 1);
}
// 如果栈不为空，找到了一组合法的括号序列，左括号是刚刚弹出的元素，长度可以通过 i - stack.peek() 获取
else{
result = Math.max(result, i - stack.peek());
}
}
}
}
// 返回结果
return result;
}
}2、Python
class Solution(object):
def longestValidParentheses(self, s):
# 创建栈空间
stack = []
# result 记录最长有效（格式正确且连续）括号子串的长度
result = 0
# 设置变量 leftStart 表示合法括号序列的起始索引位置，指向一个左括号，初始值为 0
leftStart = 0
# 循环遍历字符串数组
for i in range(len(s)):
# 访问左括号时，把它存储到栈里
if s[i] == '(':
stack.append(i)
# 访问右括号时
else :
# 如果当前栈为空，说明这个右括号在前面没有和它匹配的左括号，那么 leftStart 需要发生改变
if not stack:
# 索引变为当前字符的下一个
leftStart = i + 1
else :
# 移除栈顶元素
stack.pop()
# 如果此时栈为空，说明当前右括号为右端点的合法括号序列的左端点为 leftStart，则更新长度 i - leftStart + 1
if not stack:
result = max(result, i - leftStart + 1)
# 如果栈不为空，找到了一组合法的括号序列，左括号是刚刚弹出的元素，长度可以通过 i - stack[-1] 获取
else :
result = max(result, i - stack[-1])
# 返回结果
return result
