最长有效括号 - 困难 - 算法题 - 算法 - 计算机

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

示例 1：

示例 2：

示例 3：

	输入：s = ""
	输出：0

提示：

	0 <= s.length <= 3 * 104
	s[i] 为 '(' 或 ')'

解法一：栈

	/**
	* 栈
	*
	* 我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：
	*
	* 对于遇到的每个 '(' ，我们将它的下标放入栈中
	* 对于遇到的每个 ')' ，我们先弹出栈顶元素表示匹配了当前右括号：
	* 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
	* 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
	*
	*/
	public int longestValidParentheses2(String s) {
	Stack<Integer> stack = new Stack<>();
	// 如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，
	// 这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，
	// 我们在一开始的时候往栈中放入一个值为 -1 的元素。
	stack.push(-1);
	int max = 0;
	char[] array = s.toCharArray();
	for (int i = 0; i < s.length(); i++){
	// 当为左括号时，将当前进栈
	if (array[i] == '('){
	stack.push(i);
	}else {
	// 当为右括号时出栈
	stack.pop();
	// 如果栈为空，将当前右括号位置入栈
	if (stack.empty()){
	stack.push(i);
	}else {
	// 否则由当前位置 - 栈顶元素
	max = Math.max(max, i - stack.peek());
	}
	}
	}
	return max;
	}

解法二：正向逆向结合

	/**
	* 正向逆向结合
	*
	* 我们利用两个计数器 left 和 right 。首先，我们从左到右遍历字符串，
	* 对于遇到的每个‘(’，我们增加 left 计数器，对于遇到的每个‘)’ ，
	* 我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，
	* 并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。
	*
	*/
	public int longestValidParentheses1(String s) {
	int length = s.length();
	int left = 0, right = 0, max = 0;
	// 从左往右跑
	for (int i = 0; i < length; i++){
	// 统计左括号和右括号的数量
	if (s.charAt(i) == '('){
	left++;
	}else {
	right++;
	}
	// 当两个括号数量一致时，统计最大数量
	// 当右括号大于左括号数量时，重置
	if (left == right){
	max = Math.max(max, right * 2);
	}else if (right > left){
	left = right = 0;
	}
	}

	// 从右往左跑
	left = right = 0;
	for (int i = length - 1; i >= 0; i--){
	// 统计左括号和右括号数量
	if (s.charAt(i) == '('){
	left++;
	}else {
	right++;
	}
	// 当两个括号数量一致时，统计最大数量
	// 当左括号大于右括号数量时，重置
	if (left == right){
	max = Math.max(max, left * 2);
	}else if (left > right){
	left = right = 0;
	}
	}
	return max;
	}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses