题目描述
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example1:
Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
解题思路
- 参考
- 借助栈来求解，需要定义个 start 变量来记录合法括号串的起始位置
- 遍历字符串，如果遇到左括号，则将当前下标压入栈， -》 当前下标
- 如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到 start，
- 如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和 i - start + 1 中的较大值，
- 否则更新结果和 i - st.top() 中的较大值
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
int res = 0;
int start = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == '('){
st.push(i);
}else if(s[i] == ')'){
if(st.empty()){
start = i + 1;
// continue;
}else{
st.pop();
if(st.empty()){
res = max(res, i - start + 1);
}else{
res = max(res, i - st.top());
}
}
}
}
return res;
}
};
