32. 最长有效括号

🔴   🔖  栈 字符串 动态规划  🔗 LeetCode

题目

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

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 * 10^4
• s[i] is '(', or ')'.

题目大意

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

解题思路

使用栈来解决这道题。

• 保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，初始化为 -1；

• 栈里其他元素维护左括号的下标。

• 从前往后遍历字符串:

  • 对于遇到的每个 '(' ，将它的下标放入栈中；
  • 对于遇到的每个 ')' ，先弹出栈顶元素表示匹配了当前右括号；
  • 如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新之前提到的「最后一个没有被匹配的右括号的下标」；
  • 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」；

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串的长度，需要遍历整个字符串；
• 空间复杂度：O(n)，栈的大小在最坏情况下会达到 n。

代码

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
	let stack = [-1],
		res = 0;
	for (let i = 0; i < s.length; i++) {
		const char = s[i];
		if (char == '(') {
			stack.push(i);
		} else {
			stack.pop();
			if (stack.length == 0) {
				stack.push(i);
			} else {
				res = Math.max(res, i - stack[stack.length - 1]);
			}
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
20	有效的括号	[✓]	栈 字符串