leetcode-032

题目

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

Example1

1
2
3

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

Example2

1
2
3

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

分析

这道题的意思是给出一个只含有小括号符"("和")"的字符串，求出这个字符串中能够成功进行括号匹配的子串的长度，虽然看起来与括号匹配类似，但由于是求能够匹配成功的子串，因此难度加大了不少。

解法

一开始我致力于在括号匹配算法的基础进行改进，以求得最长的可以匹配的子串。但这个想法似乎很难实现，因为我不知道在括号能够匹配时它的子串中的具体位置，例如：

对于"((()()))"这个字符串，括号匹配算法遍历到第4个字符')'才能第一次匹配成功,随后在第6，7，8个字符时可以连续匹配成功3次，但是如何知道后两次成功匹配的字符都分别在子串的首尾部呢？这比较难求，我们也不关心这个，因此不如在匹配成功时计算长度。

但是要求出长度也不是那么容易的，因为括号匹配算法遍历字符串时，我们不能预测接下来的字符能否与之前栈里的字符成功匹配，例如：

对于"((()()(()"这个字符串，最大匹配成功的子串长度为4，但要是它后面还有一个字符')'，即字符串"((()()(())"，那最大匹配成功的子串长度就是8了；如果接下来的字符是'('，答案就还是4。其中的区别在于，如果两个能成功匹配的子串相邻，那自然就有了更长的符合条件的子串。

那怎么判断相邻的子串呢？考虑到只有遍历到的字符是')'时才有可能匹配成功，我们可以通过判断匹配后(会弹出栈顶的'('元素)栈是否为空来入手：

如果栈为空，就代表在这一对匹配的括号前面没有其他符号来阻隔它与之前的子串，即它与之前匹配的子串相邻，可以加长子串了(当然也不一定是前面，毕竟这一对括号可能分别在之前子串的首尾部)
如果栈不为空，那就说明当前匹配的括号与之前子串不相邻，但由于栈中还有'('字符，可能与之后的字符匹配，因此不需要变化start

算法思路如下：

用变量result和start来记录当前最大匹配的子串长度和当前匹配的子串首字符位置
利用括号匹配算法，遍历字符串，遇到'('把它的下标压栈，而')'则不压栈
若遇到')'，需谨慎处理：
- 如果栈为空，则由于')'一定不会与之后的字符匹配，因此前面的子串一定不会与后面的子串相邻了，start = indexOf(')') + 1，即现在要匹配的子串首字符从')'下一个字符开始
- 如果栈不为空，那一定会匹配(栈里面只有'(')，因此弹出栈顶，继续判断
  - 如果弹出栈后栈空，则匹配的子串相邻，需要更新result，方法是判断result和当前匹配子串长度哪个大
  - 否则子串不相邻(这是暂时的，因为start还没有变化)，更新result，不需要与之前的子串比较，因为已经比较过了，比较当前匹配的就好

可以找出一些字符串例子来帮助理解这个思路。

代码

#include<iostream>
#include<string>
#include<stack>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string str) {
        int result = 0, start = 0;
        stack<int> s;
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == '(') s.push(i);
            else {
                if (s.empty()) start = i + 1;
                else {
                    s.pop();
                    if (s.empty()) result = max(result, i - start + 1);
                    else result = max(result, i - s.top());  //已经pop过一次了，所以不需要再加1
                }
            }
        }
        return result;
    }
};

int main() {
    Solution s;
    cout << s.longestValidParentheses("()(()");
}

算法时间复杂度为O(n)，空间复杂度为O(n)