深圳营销网站设计网站设计论文分类号

32. 最长有效括号

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

子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

有事会暂停更新，总之慢慢积累，今天看一下这道题，有动态规划、栈等解法，本题采用计数器法，思路就是分别定义两个计数器left和rigth，首先从左向右遍历，当遇到左括号时left++，遇到右括号时right++，当left == right时记录此时有效子串的长度maxLength，当right > left时，重置left和right为0，遍历结束后不一定能得到最长有效括号的长度，因为如果输入的是“((((((()”时，此时如果从左向右遍历maxLength依旧为0，我们需要从右向左遍历，需要改变的条件是当left > right时，重置left和right为0，两次不同方向遍历结束后就可以得到maxLength了，时间复杂度为O（n）,空间复杂度为O（1），代码如下

class Solution {public int longestValidParentheses(String s) {int left = 0, right = 0, maxLength = 0;// 从左向右遍历for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {left++;} else {right++;}if (left == right) {maxLength = Math.max(maxLength, right * 2);} else if (right > left) {left = right = 0;}}left = right = 0;// 从右向左遍历for (int i = s.length() - 1; i >= 0; i--) {if (s.charAt(i) == ')') {right++;} else {left++;}if (left == right) {maxLength = Math.max(maxLength, left * 2);} else if (left > right) {left = right = 0;}}return maxLength;}
}

题目链接：题单 - 力扣（LeetCode）全球极客挚爱的技术成长平台