32. 最长有效括号 (opens new window)

1.栈

解题思路：初始化两个栈，一个用于匹配括号；另一个栈用于保存已匹配的连续括号起始索引下标。

• 本题扩充了栈匹配的使用技巧，栈中存放的是字符串中每一个字符的索引下标，这样的做法比直接存储每一个字符能够获取到更多的信息。

• 另外解题的关键在于如何理解连续最长有效括号：在栈中保存每个连续有效括号的起始索引下标，每次成功匹配括号时，在有序括号列表对应两种操作①更新有序括号长度②添加新的有序括号。更新方法有三种：

  • 包含型：当前匹配成功的括号和栈顶有序括号属于包含关系，比如 (())，因此栈顶元素头尾索引都要更新。

  • 连续型：当前匹配成功的括号和栈顶有序括号属于并列的关系，比如()()，因此栈顶元素尾索引需要更新。

  • 上面两种更新方式还隐含派生出另一种更新方式，当包含型更新使头尾索引的范围扩大时，头索引可能会碰到前一个有效括号的尾索引，引发连续型更新。这就意味着有效括号不能只保存前一个序列，而要保存所有出现过的有效序列，每次有序括号的长度得到更新时都有可能导致和前一个有序括号合并。

    具体例子："( ) ( ( ( ( ) ( ( ) ) ) ) ) "

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        Stack<int[]> last = new Stack<>();
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.size() == 0 || s.charAt(stack.peek()) == ')') {
                    stack.push(i);
                    continue;
                }
                if (s.charAt(stack.peek()) == '(') {
                    int top = stack.pop();
                    if (last.size() == 0) {
                        last.add(new int[]{top, i});
                    } else {
                        while (last.size() > 0) {
                            int[] peek = last.peek();
                            if (peek[0] == top + 1 && peek[1] + 1 == i) {
                                last.pop();
                                res = i - top + 1 > res ? i - top + 1 : res;
                            } else if (peek[1] + 1 == top) {
                                last.pop();
                                top = peek[0];
                                res = i - top + 1 > res ? i - top + 1 : res;
                            } else {
                                last.push(new int[]{top, i});
                                break;
                            }
                        }
                        if (last.size() == 0) {
                            last.push(new int[]{top, i});
                        }
                    }
                    res = i - top + 1 > res ? i - top + 1 : res;
                }
            }
        }
        return res;
    }
}

2.优化

• 后来发现更新方式想复杂了，实际上只有一种更新方式，那就是连续型更新。原因在于通过栈的方式匹配括号，已经自带了包含型的判断条件，也就是说只要在栈中能够匹配上一个有效括号，那么当前括号内部(....)肯定保证都是有效的。也就是说“( ( ) ( )”肯定不会出现这样的包含型括号。所以问题就转化为了找到一个最长连续上下界的问题。

• 解题关键：想明白一个问题，如果当前栈顶元素索引下标为5，而当前匹配的字符索引下标为8，也就说是5到8之间是一个包含型括号，而5出栈后的栈顶元素为2，那么是否就可以说明，2到8之间也是一个有效括号(不论是否连续)。

  因此可以利用每次括号出栈后的栈顶元素，它记录着以当前字符结尾的最长有效括号的头索引。这表示当前索引和栈顶元素头索引之间的所有符号都已经被匹配挖出去了。

class Solution {
    public int longestValidParentheses(String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.add(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.add(i);
            } else {
                int curr = stack.peek();
                if (curr!=-1&&s.charAt(curr) == '(') {
                    stack.pop();
                    res = i - stack.peek() > res ? i - stack.peek() : res;
                } else {
                    stack.add(i);
                }
            }
        }
        return res;
    }
}