Problem

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

来源：力扣（LeetCode）

Example1

Input: “(()” Output: 2 Explanation: The longest valid parentheses substring is “()”

Example2

Input: “)()())” Output: 4 Explanation: The longest valid parentheses substring is “()()”

Solution

一个合法的括号序列满足下面两条性质

class Solution { public: int longestValidParentheses(string s) { int ret = 0; int start = -1; //分段起点的前一个位置 stack<int> stk; for(int i = 0;i<s.length();++i) { if(s[i] == '(')//左括号直接入栈 { stk.push(i); } else { if(!stk.empty())//当前是右括号，且栈里还有左括号 { stk.pop();//左括号弹栈 if(!stk.empty())//如果栈不为空，即还有左括号 { ret = max(ret,i - stk.top()); } else如果栈不为空，即没有左括号，说明当前的右括号可以匹配这一段最左侧的左括号 { ret = max(ret,i - start); } } else//当前是右括号，栈里没有左括号，说明该右括号是使得右括号数量大于左括号数量的第一个位置 { start = i; } } } return ret; } };