算法题-最长有效括号

题目链接：https://leetcode-cn.com/problems/longest-valid-parentheses/ 题目描述： 给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

解法一

使用栈来存储元素下标，从下标来计算长度。 时间复杂度：O(N)，N为字符串长度，遍历每个字符串元素。 空间复杂度：O(N)，栈的大小最坏会达到O(N)。

class Solution { public int longestValidParentheses(String s) { int maxans = 0; //栈中存放元素的下标 Deque<Integer> stack = new LinkedList<>(); //栈底存放最新没有匹配的右括号的下标，作为下一个有效括号子串的开端 //将初始化-1入栈，作为下一个有效子串的开端 stack.offerFirst(-1); for(int i=0;i<s.length();i++) { //如果是左括号，就将其下标入栈 if(s.charAt(i) == '(') { stack.offerFirst(i); } //如果是右括号 else { //将栈顶元素出栈 stack.pollFirst(); //如果栈空了，说明这个右括号没有匹配，将其下标入栈 if(stack.isEmpty()) { stack.offerFirst(i); } //如果栈没空，说明是有效子串，计算其最长长度 else { maxans =Math.max(maxans,i - stack.peekFirst()); } } } return maxans; } }

解法二：

动态规划 时间复杂度：O(N) 空间复杂度：O(N)

public class Solution { public int longestValidParentheses(String s) { int[] dp = new int[s.length()]; int result = 0; //记录左括号的数量 int leftCount = 0; for (int i = 0; i < s.length(); i++) { //如果是左括号，计数加1 if (s.charAt(i) == '(') { leftCount++; } //如果是右括号并且leftCount>0 else if (leftCount > 0){ //又有一对括号有效，加2 //dp[i]=dp[i-1]+2 dp[i] = dp[i - 1] + 2; //再找到当前右括号对应的左括号位置之前的位置i-dp[i]（如果有的话） //再加上它记录的之前的有效子串的长度 dp[i] += (i - dp[i]) >= 0 ? dp[i - dp[i]] : 0; //结果选择更大的那个 result = Math.max(result, dp[i]); //同时将当前右括号对应的左括号减去，计数-1 leftCount--; } } return result; } }

解法三

使用两个指针，分别记录左右括号的个数。 两次循环遍历，分别处理右括号多于左括号的情况，和左括号多于右括号的情况，和数量相等为有效子串的情况。 时间复杂度：O(N)，空间复杂度：O(1)

class Solution { public int longestValidParentheses(String s) { int res=0; //记录左括号数量 int left=0; //记录右括号数量 int right=0; //正向遍历，处理右括号比左括号多的情况 for(int i=0;i<s.length();i++) { //是左括号，左括号计数加1 if(s.charAt(i) == '(') { left++; } //是有括号，右括号计数加1 else { right++; } //如果左右括号数相等，则是有效括号，计算长度 if(left == right) { res = Math.max(res,2*right); } //如果右括号比左括号多，要重新开始计数 else if(right>left) { left = right = 0; } } //反向再遍历一次，处理左括号比右括号多的情况 left = right = 0; for(int i=s.length()-1;i>=0;i--) { if(s.charAt(i) == '(') { left++; } else { right++; } if(left == right) { res = Math.max(res,2*left); } else if(left > right) { left = right = 0; } } return res; } }