每日题解:LeetCode 32. 最长有效括号

题目地址 个人博客地址

题目描述

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

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

解法

java 栈

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

cpp

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

解题思路

这道题目要求找出最长有效括号子字符串，返回其长度。 1、有效括号子字符串:要求字符串必须满足(、)数量相等；同时一个(必有有一个)对应，比如(())就是有效字符，)(就不是有效字符 2.最长:要求字符必须连续，()(()

栈

栈的比较简单，遍历字符串，遇到(就存入栈，直到遇到对应的)就弹出最近的一个(元素，就，由于计算长度，这里我们栈中的元素存入的是字符的下标 但是我们遇到一个问题， 如图，当我们遍历到下标0的时候，此时栈为空，此时元素是否入栈？ 如果不入栈，当遍历到下标4的时候，由于栈为空，我们按照计算(当前下标-栈顶下标)+1,这里就会丢失掉之前字符长度信息，所以，需要一个参照物。 即栈为空时，遇到)，存入栈作为参照物 比如我们遍历到4的下标时，此时栈顶下标时0，当前的最长字符长度就是4了，即栈顶需要维护最后一个没有被匹配的右括号的下标，同时栈初始化的，就存入一个-1的参照物，避免第一个字符就是 ),stack.pop();异常

if (s.charAt(i) == '(') { stack.push(i); } else { stack.pop(); if (stack.empty()) { stack.push(i); } else { ans = Math.max(ans, i - stack.peek()); } }

计数

首先，我们使用两个变量left、right分别记录下遇到的(、)的个数，由于是连续的字符串，当left的个数和right个数相等时，则认为字符有效，但是遇到right>left，说明字符串中，我们将left、right置零， 如图中所示，当遍历到下标0时，此时，right=1，left=0,就需要重新进行计数了

int ans = 0, left = 0, right = 0, len = s.length(); for (int i = 0; i < len; ++i) { if (s[i] == '(') { left++; } else { right++; } if (left == right) ans = max(ans, left << 1); else if (right > left) { left = right = 0; } }

但是，这种从左往右遍历，只能解决掉右括号的个数大于作括号的情况，遇到这种(()，就没法导出结果了,所以就需要从右往左再遍历一次，此时我们需要将置零的条件改成与之前的相反就可以了left > right

for (int i = len-1; i >=0; --i) { if (s[i] == '(') { left++; } else { right++; } if (left == right) ans = max(ans, left << 1); else if (left > right) { left = right = 0; } }