【LeetCode】32.Longest Valid Parentheses 最长合法序列

一、概述

输入一个只包含左括号和右括号的字符串，输出其最长合法序列的长度。

什么叫最长合法序列呢？就是在此序列中，不改变顺序，每一个左括号的后面总有一个右括号与之对应。例如

((()))

()()()

但是

))((

这种不是。

二、分析

1、我的思路

最开始我的思路类似之前写Valid Parentheses一样，用栈保存左括号，有一个有括号就出栈一个。但是问题来了：

如果只有一个合法子序列，那么：

左括号剩余，那右括号数量*2就是合法序列长度；右括号剩余，那么左括号*2就是合法序列长度。

但是如果不止一个合法子序列呢？

我们该如何延长一个合法子序列的长度呢？

我想到这样一种方法：

已经有一对()，现在又出现了(，往后如果这个()能作为子序列头，则这个)后面的左括号压入一个新栈，然后弹出，直到栈空，这样就可以延长这一子序列的长度。

但是太麻烦了。有好多子序列得多少栈啊。边界条件也难以界定。

于是我选择了一个十分直观的方法：

多次遍历输入序列，每次遇到()，把它们变成**，如果遇到*，那么接着往下，无视它。

直到最后所有的()都变成**。

然后找到最长的*子序列，其长度就是结果。思路很简单，因此实现也很简单。代码如下：

class Solution {
public:
    int longestValidParentheses(string s) {
        int len=s.size();
        if(len<=1)
            return 0;
        int num=-1;
        int now=0;
        int first=-1;
        while(num<now)
        {
            num=now;
            first=-1;
            for(int i=0;i<len;++i)
            {
                if(s[i]=='(')
                {
                    first=i;
                }
                else if(first!=-1&&s[i]==')')
                {
                    s[first]='*';
                    first=-1;
                    s[i]='*';
                    now=now+2;
                }
                else
                    continue;
            }
        }
        int sum=0;
        int max=0;
        for(int i=0;i<len;++i)
        {
            if(s[i]=='*')
            {
                ++sum;
            }
            else
            {
                if(max<sum)
                    max=sum;
                sum=0;
            }
        }
        if(max<sum)
            return sum;
        return max;
    }
};

有几个地方要注意，每次进入循环的时候，要先更新当前的最大长度，重置first。

别看时空复杂度好像很不错，但是我这是重复提交四次选最好的，这玩意太不准了：

2、较好的算法

我想不出，只是在底下喊666的份儿。但是看还是能看明白的：

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);
        int maxL=0;
        for(int i=0;i<s.size();i++)
        {
            int t=stk.top();
            if(t!=-1&&s[i]==')'&&s[t]=='(')
            {
                stk.pop();
                maxL=max(maxL,i-stk.top());
            }
            else
                stk.push(i);
        }
        return maxL;
    }
};

他用了一个栈，并且只循环了一次。这个栈中保存什么呢？保存的元素可以按如下形式描述：

如果循环在当前中断，栈中元素都是没能匹配的废物元素，是一群单身狗。

举例子更恰当：

序列为) ( ) ( ) ) ( ) ( ) (

首先 ) 入栈；然后 ( 入栈；然后判断可知 ) 可以和栈顶的 ( 匹配。如果到这里循环中断，第一个 ) 就是单身狗。

但是没中断，因此目前栈顶的 ( 弹出；每次执行弹出操作后都会更新子序列长度的最大值。

这也就是该算法的核心：

子序列如何划分？什么样的元素能够把子序列划分开？

答案就是废物元素。也就是，当前的栈顶元素就是当前子序列的开头，当前循环到的元素就是当前子序列的末尾。这很重要，可能有点难理解。

然后 ( 入栈。。。。。。

最后栈里面剩什么呢？剩下 ) ) ( 正好是三个废物。它们在主序列中划分出两个子序列，长度都是4。因此结果为4。

我觉得，能够想出这个思路，要对问题有一个清晰的认识：

找最长合法子序列->子序列是什么？->如何划分子序列？->归纳推理，保存子序列的起点，动态更新终点，也就动态更新了长度。

自叹弗如。

三、总结

多观察，多思考，多做题。没别的了。