Longest Valid Parentheses
Total Accepted: 63715 Total
Submissions: 282480 Difficulty: Hard
Given a string containing just the characters '(' and ')',
find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses
substring is "()", which has length = 2.
Another example is ")()())", where the longest
valid parentheses substring is "()()", which has length = 4.
Subscribe to see which companies asked this question
Hide Tags
Dynamic Programming String
Hide Similar Problems
(E) Valid Parentheses
思路：
使用stack来保存未匹配的“括号”的下标，然后求下标之间的最大差值。
c++ code:
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
stack<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') st.push(i);
else {
if (!st.empty()) {
if (s[st.top()] == '(') st.pop();
else st.push(i);
}
else st.push(i);
}
}
int a = n, b = 0;
int ans = 0;
while(!st.empty()) {
b = st.top();
st.pop();
ans = max(ans, a-b⑴);
a = b;
}
ans = max(ans, a);
return ans;
}
};