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

题目描述

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

题目分析

栈：先进后出

思路：可参考『刷题LeetCode：20.有效的括号』，加上求最大值的逻辑

代码实现

public class LongestValidParentheses32 {


    public static void main(String[] args) {
        LongestValidParentheses32 result = new LongestValidParentheses32();
        System.out.println(result.longestValidParentheses("()()()))))))))(((()()"));
    }



    /**
     * 【方法 1：栈】
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     *
     *
     * 时间复杂度： O(n)，n 是给定字符串的长度。我们只需要遍历字符串一次即可。
     *
     * 空间复杂度： O(n)。栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n) 。
     *
     */
    public int longestValidParentheses(String s) {

        int maxLen = 0;
        int length = s.length();

        LinkedList<Integer> stack = new LinkedList<Integer>();
        stack.addLast(-1);

        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.addLast(i);
            }
            if (ch == ')') {
                stack.removeLast();
                if (stack.isEmpty()) {
                    // 未匹配到 "("
                    stack.addLast(i);
                } else {
                    // 匹配到 "("
                    if ((i - stack.getLast()) > maxLen) {
                        maxLen = i - stack.getLast();
                    }
                }
            }
        }

        return maxLen;

    }


}

复杂度

• 时间复杂度：O(logn)，其中 n 是定版本的数量。
• 空间复杂度：O(n)。栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n) 。

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
�