这是我参与更文挑战的第29天，活动详情查看：更文挑战

前言

力扣第三十二题 最长有效括号 如下所示：

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

示例 1：

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

示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3：

输入：s = “”
输出：0

一、思路

这一题因为有这种一一对应的关系，所以第一眼看到就很自然的想到了使用栈来解决。

要想知道最长的有效括号有两个关键点，如下所示：

任何一个有效的括号都是以 ) 结尾
有效的括号的长度是 ) 的下标减去 ( 的下标再加 1，举个例子 ()(()) 的长度是下标 5 - 0 + 1 = 6

为了解决在迭代过程中无法得知子串的连续性，我们在栈底维护一个起始连续位置（官方称为最后一个右括号的位置）。这么做其实是为了解决类似于 ()(()) 的情况，栈只能知道最后一个 ) 匹配的是倒数第四个 (，栈无法知道在倒数第四个 ( 还有没有连续的有效字符串。所以起始时将栈底元素置为 -1，这样最后一个 ) 出栈时，用当前下标 5 - (-1) 即可得到结果 6。

对于连续性来讲，即使子串为 ()(()，它也是连续的。还有什么时候会破坏连续性呢？就是当前出现了无法匹配的 ) 时，如 ())(())，第三个元素 ) 出现了无法匹配的情况，所以在第三个元素之后起始连续位置就变为了下标 2

具体实现的话，主要就是在迭代字符串的过程中，会有以下两种情况：

碰到 (：将当前左括号的下标入栈
碰到 ) 先出栈
- 如果栈为空：说明连续性被破坏，更新栈底元素为当前下标。
- 如果栈不为空：用当前下标减去栈顶元素的值就是当前 ) 对应的 ( 中间的长度

举个例子

这里以 s = ())(()) 作为例子，具体的步骤如下所示：

初始化栈底元素 -1
开始迭代，获取到第一个字符 (。( 的下标 0 入栈，此时栈中元素为 0, -1
获取到第二个字符 )。栈顶 0 出栈，并用当前下标减栈顶元素 1 - (-1) = 2，更新结果 ret = 2
获取到第三个个字符 )。栈顶 -1 出栈，栈为空，更新栈底起始连续位置为 2
获取到第四个字符 (。( 的下标 3 入栈，此时栈中元素为 3, 2
获取到第五个字符 (。( 的下标 4 入栈，此时栈中元素为 4, 3, 2
获取到第六个字符 )。栈顶 4 出栈，并用当前下标减栈顶元素 5 - 3 = 2，无需更新结果
获取到第七个字符 )。栈顶 3 出栈，并用当前下标减栈顶元素 6 - 2 = 4，更新结果 ret = 4

二、实现

实现代码

实现代码与思路中保持一致

    /**
     * java使用栈实现
     */
    public int longestValidParentheses(String s) {
        int ret = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            // 左括号入栈
            if ('(' == c) {
                stack.push(i);
            } else {    // 右括号有两种情况
                stack.pop();
                if (stack.isEmpty())    // 不匹配更新起始连续的位置
                    stack.push(i);
                else    // 更新结果
                    ret = Math.max(ret, i - stack.peek());
            }
        }
        return ret;
    }
复制代码

测试代码

    public static void main(String[] args) {
        int ret = new Number32().longestValidParentheses("()(()");
        System.out.println(ret);
    }
复制代码