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

Author Avatar
清水雅然君 07月 05,2020

题目地址
个人博客地址

题目描述

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

示例 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;
            }
        }