32. Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses
substring
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = ""
Output: 0
Constraints:
0 <= s.length <= 3 * 104
s[i] is '(', or ')'.
|
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int longestValidParentheses(string s) {
stack<int> st;
int maxans = 0;
int i = -1;
st.push(i);
for (i = 0; i < s.size(); i++) {
if (s[i] == '(') {
st.push(i);
} else {
st.pop();
if (st.empty()) {
st.push(i);
} else {
maxans = max(maxans, i - st.top());
}
}
}
return maxans;
}
|
