32. Longest Valid Parentheses

题目描述

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

解题思路

括号匹配是一道非常经典的问题。考虑一个字符串 $s=a_1a_2a_3...a_n$ ，如果这是一个括号能成功匹配的字符串，它应该具有这样的性质：前括号和反括号的数量相等；在这个前提下，对于s的子串 $s_k=a_0...a_k$ ，若 $a_{k+1}$ 是反括号，那么， $s_k$ 中的前括号一定比反括号要多。

根据这两个性质，要判断一个字符串可以考虑这样的策略：用栈来处理这个字符串。遇到前括号时，将前括号入栈；遇到反括号时，若栈顶为空，则说明子串 $s_k$ 前括号与反括号一样多，不符合条件，该串不合法；若栈顶不为空，则将栈顶出栈。最后若栈为空，则合法。

在这道题里，我们也可以用这个策略来判断串s是否为合法的括号匹配字符串，若s是合法的括号匹配字符串，则最长子括号匹配字符串的长度就是s的长度。但如果不是呢？我们要如何找出s中最长的括号匹配字符串呢？

假设s是这样的字符串： $t_0p_0t_1p_1...t_np_nt_{n+1}$ ，t为合法的括号匹配字符串，而p则是夹在它们中的非法字符（注意，这里t可以是空串，因为空串也是合法的括号匹配字符串）。我们继续用上面提到的方法来遍历这个字符串，不同的是，在遇到不合法的情况的时候不退出。在遍历完一遍之后，栈中留存的是串 $p_0...p_n$ ，因为夹在它们中间的串都会能正确匹配，最后留下空的栈空间。在找到这些夹在中间的元素之后，我们就可以通过计算p的下标的差值的方式，找到最长的子串。最后返回最大的差值即可。

要注意一下长度的计算公式：

$j=0: L(t_0)=I(p_0)$

$1 \leq j \leq n: L(t_j)=I(p_j)-I(p_{j-1})-1$

$j=n+1: L(t_{n+1})=s.length()-I(p_{j-1})-1$

时间复杂度分析

遍历一次字符串，遍历栈中剩下的元素:O(n)

空间复杂度分析

最多为n，最小为0。最大空间复杂度为O(n)

源码

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.length() == 0) {
            return 0;
        }
        stack<int> indexStack;
        stack<char> st;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                st.push(s[i]);
                indexStack.push(i);
            } else {
                if (!st.empty() && st.top() == '(') {
                    st.pop();
                    indexStack.pop();
                } else {
                    st.push(s[i]);
                    indexStack.push(i);
                }
            }
        }
        if (st.empty()) {
            return s.size();
        } else {
            int lastIndex = s.length(), beginIndex = 0;
            int longest = 0;
            while (!indexStack.empty()) {
                beginIndex = indexStack.top();
                cout << beginIndex << endl;
                indexStack.pop();
                longest = max(longest, lastIndex - beginIndex - 1);
                lastIndex = beginIndex;
            }
            return max(longest, lastIndex);
        }
    }
};

32. Longest Valid Parentheses(week11)