32. 最长有效括号

题目描述

输入一个只含 '(' 和 ')' 的字符串 s。

如果一段括号串里每个左括号都能找到后面的右括号将它闭合，且没有多余的右括号，它就是有效的，例如 "(()())"。

在 s 的所有连续子串中，找出最长的有效括号串，返回其长度。没有则返回 0。

示例 1

输入：s = "(()"
输出：2

解释：最长的有效子串是 "()"。

示例 2

输入：s = ")()())"
输出：4

解释：最长的有效子串是 "()()"。

示例 3

输入：s = ""
输出：0

解释：空串没有有效子串。

数据范围

0 <= s.length <= 3 * 10^4
s[i] 只能是 '(' 或 ')'。

解题思路：下标栈

栈保存未匹配括号的下标，栈底放当前有效片段左边界；遇到右括号配对后用 i-stack[-1] 更新答案。

为什么正确

栈底是最近一个不能作为有效片段一部分的位置，栈中其他位置是未匹配左括号。

复杂度分析

时间 O(n)，空间 O(n)。

易错点

栈底边界不能省略；遇到无法匹配的右括号时必须把它设为新的边界。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        answer = 0
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    answer = max(answer, i - stack[-1])
        return answer

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int answer = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    answer = Math.max(answer, i - stack.peek());
                }
            }
        }
        return answer;
    }
}

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> stack = {-1};
        int answer = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == '(') {
                stack.push_back(i);
            } else {
                stack.pop_back();
                if (stack.empty()) {
                    stack.push_back(i);
                } else {
                    answer = max(answer, i - stack.back());
                }
            }
        }
        return answer;
    }
};

func longestValidParentheses(s string) int {
	stack := []int{-1}
	answer := 0
	for i, ch := range s {
		if ch == '(' {
			stack = append(stack, i)
		} else {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				stack = append(stack, i)
			} else {
				answer = max(answer, i-stack[len(stack)-1])
			}
		}
	}
	return answer
}

var longestValidParentheses = function(s) {
    const stack = [-1];
    let answer = 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 {
                answer = Math.max(answer, i - stack[stack.length - 1]);
            }
        }
    }
    return answer;
};

function longestValidParentheses(s: string): number {
    const stack: number[] = [-1];
    let answer = 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 {
                answer = Math.max(answer, i - stack[stack.length - 1]);
            }
        }
    }
    return answer;
};

载入编辑器，自己跑一遍 →

其他解法

三种方法都是 O(n) 时间；栈和动态规划需要 O(n) 空间，左右两遍计数只用 O(1) 空间。

解法 2：动态规划时间 O(n)，空间 O(n)

dp[i] 表示以 s[i] 结尾的最长有效子串长度，只有 s[i] 为 ) 时才可能非 0。若 s[i-1] 是 (，两者配对，dp[i] = dp[i-2] + 2。若 s[i-1] 也是 )，就跳过以 i-1 结尾的有效段，看它前面的位置 j = i - dp[i-1] - 1；若 s[j] 是 (，则 dp[i] = dp[i-1] + 2 + dp[j-1]，最后一项把紧邻在前的有效段也连上。答案是 dp 的最大值。

把「有效段可以嵌套和拼接」写成显式的状态转移，是练习序列 DP 的好例子。边界下标较多，比栈更容易写错。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        dp = [0] * n
        answer = 0
        for i in range(1, n):
            if s[i] != ')':
                continue
            if s[i - 1] == '(':
                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
            else:
                j = i - dp[i - 1] - 1
                if j >= 0 and s[j] == '(':
                    dp[i] = dp[i - 1] + 2 + (dp[j - 1] if j >= 1 else 0)
            answer = max(answer, dp[i])
        return answer

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length(), answer = 0;
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != ')') continue;
            if (s.charAt(i - 1) == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else {
                int j = i - dp[i - 1] - 1;
                if (j >= 0 && s.charAt(j) == '(') {
                    dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
                }
            }
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }
}

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), answer = 0;
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] != ')') continue;
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else {
                int j = i - dp[i - 1] - 1;
                if (j >= 0 && s[j] == '(') {
                    dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
                }
            }
            answer = max(answer, dp[i]);
        }
        return answer;
    }
};

func longestValidParentheses(s string) int {
	n, answer := len(s), 0
	dp := make([]int, n)
	for i := 1; i < n; i++ {
		if s[i] != ')' {
			continue
		}
		if s[i-1] == '(' {
			dp[i] = 2
			if i >= 2 {
				dp[i] += dp[i-2]
			}
		} else {
			j := i - dp[i-1] - 1
			if j >= 0 && s[j] == '(' {
				dp[i] = dp[i-1] + 2
				if j >= 1 {
					dp[i] += dp[j-1]
				}
			}
		}
		if dp[i] > answer {
			answer = dp[i]
		}
	}
	return answer
}

var longestValidParentheses = function(s) {
    const n = s.length;
    const dp = new Array(n).fill(0);
    let answer = 0;
    for (let i = 1; i < n; i++) {
        if (s[i] !== ')') continue;
        if (s[i - 1] === '(') {
            dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
        } else {
            const j = i - dp[i - 1] - 1;
            if (j >= 0 && s[j] === '(') {
                dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
            }
        }
        answer = Math.max(answer, dp[i]);
    }
    return answer;
};

function longestValidParentheses(s: string): number {
    const n = s.length;
    const dp: number[] = new Array(n).fill(0);
    let answer = 0;
    for (let i = 1; i < n; i++) {
        if (s[i] !== ')') continue;
        if (s[i - 1] === '(') {
            dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
        } else {
            const j = i - dp[i - 1] - 1;
            if (j >= 0 && s[j] === '(') {
                dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
            }
        }
        answer = Math.max(answer, dp[i]);
    }
    return answer;
}

解法 3：左右两遍计数时间 O(n)，空间 O(1)

从左往右扫描，分别统计左、右括号数。两者相等时当前段有效，用 2·right 更新答案；右括号更多时当前段已无法变有效，两个计数归零。这样会漏掉左括号始终更多的情况（如 (()），所以再从右往左扫一遍，规则对称：左括号更多时归零。两遍的最大值即为答案。

只用两个计数器，额外空间 O(1)，是空间最优解。需要理解为什么单向一遍不够、反向一遍恰好补上，不如栈直观。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        answer = 0
        left = right = 0
        for ch in s:
            if ch == '(':
                left += 1
            else:
                right += 1
            if left == right:
                answer = max(answer, 2 * right)
            elif right > left:
                left = right = 0
        left = right = 0
        for ch in reversed(s):
            if ch == '(':
                left += 1
            else:
                right += 1
            if left == right:
                answer = max(answer, 2 * left)
            elif left > right:
                left = right = 0
        return answer

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length(), answer = 0, left = 0, right = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') left++; else right++;
            if (left == right) answer = Math.max(answer, 2 * right);
            else if (right > left) left = right = 0;
        }
        left = right = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') left++; else right++;
            if (left == right) answer = Math.max(answer, 2 * left);
            else if (left > right) left = right = 0;
        }
        return answer;
    }
}

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), answer = 0, left = 0, right = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') left++; else right++;
            if (left == right) answer = max(answer, 2 * right);
            else if (right > left) left = right = 0;
        }
        left = right = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '(') left++; else right++;
            if (left == right) answer = max(answer, 2 * left);
            else if (left > right) left = right = 0;
        }
        return answer;
    }
};

func longestValidParentheses(s string) int {
	n, answer, left, right := len(s), 0, 0, 0
	for i := 0; i < n; i++ {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			answer = max(answer, 2*right)
		} else if right > left {
			left, right = 0, 0
		}
	}
	left, right = 0, 0
	for i := n - 1; i >= 0; i-- {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			answer = max(answer, 2*left)
		} else if left > right {
			left, right = 0, 0
		}
	}
	return answer
}

var longestValidParentheses = function(s) {
    const n = s.length;
    let answer = 0, left = 0, right = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] === '(') left++; else right++;
        if (left === right) answer = Math.max(answer, 2 * right);
        else if (right > left) left = right = 0;
    }
    left = right = 0;
    for (let i = n - 1; i >= 0; i--) {
        if (s[i] === '(') left++; else right++;
        if (left === right) answer = Math.max(answer, 2 * left);
        else if (left > right) left = right = 0;
    }
    return answer;
};

function longestValidParentheses(s: string): number {
    const n = s.length;
    let answer = 0, left = 0, right = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] === '(') left++; else right++;
        if (left === right) answer = Math.max(answer, 2 * right);
        else if (right > left) left = right = 0;
    }
    left = right = 0;
    for (let i = n - 1; i >= 0; i--) {
        if (s[i] === '(') left++; else right++;
        if (left === right) answer = Math.max(answer, 2 * left);
        else if (left > right) left = right = 0;
    }
    return answer;
}

栈与堆专题的其他题目

查看栈与堆全部题目 →