32. Longest Valid Parentheses
給定一個只包含字符 '(' 和 ')' 的字符串，返回最長有效（格式正確）的括號子串的長度。
範例 1：
輸入：s = "(()" 輸出：2 解釋：最長的有效括號子串是 "()"。
Python
class Solution:
def longestValidParentheses(self, s: str) -> int:
# Stack based solution
stack = [-1]
max_length = 0
for i, char in enumerate(s):
if char == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_length = max(max_length, i - stack[-1])
return max_length
17.21MB, 40ms
C++
#include <string>
#include <stack>
using namespace std;
class Solution {
public:
int longestValidParentheses(string s) {
// Stack based solution
stack<int> stk;
stk.push(-1); // Initialize stack with -1 to handle base case
int max_length = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
stk.push(i);
} else {
stk.pop();
if (stk.empty()) {
stk.push(i);
} else {
max_length = max(max_length, i - stk.top());
}
}
}
return max_length;
}
};
8.71MB, 6ms
Javascript
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
// Stack-based solution
let stack = [-1]; // Initialize stack with -1 to handle base case
let maxLength = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i);
} else {
stack.pop();
if (stack.length === 0) {
stack.push(i);
} else {
maxLength = Math.max(maxLength, i - stack[stack.length - 1]);
}
}
}
return maxLength;
};
50.87MB, 57ms
