跳至主要內容

32. 最长有效括号


32. 最长有效括号open in new window

🔴   🔖  字符串 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

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有效的括号open in new window[✓] 字符串