栈的应用之最长匹配括号长度

拼搏现实的明天。 2022-07-12 00:25 103阅读 0赞

# 最长匹配括号长度 #

主要介绍栈的一个应用，之前做过类似的题目，这次彻底搞懂，记录之。。

找到最长匹配括号长度，这题比较难，之前刷题的时候就觉得，这次学到了。  
比如说`()()()(((`最长匹配括号长度为6，`((())`最长匹配括号长度是4。

> 1.如果是左括号肯定是压栈（压入该左括号在串中的索引）。  
> 2.如果是右括号：  
> 那么就要分两种情况：  
> 第一种情况是栈不为空，说明找到了匹配的左括号，那么记录当前匹配左括号的长度，并且并且弹栈，弹栈以后又分为两种情况：  
> （1）栈为空，说明本次匹配完成，用当前索引减去start索引  
> （2）栈不为空，则当前匹配长度=当前索引-栈顶元素索引  
> 第二种情况是栈为空，说明之前已经匹配完了，那么设置当前右括号的位置为新的匹配起点开始记录。

class Solution {
    public:
        int longestValidParentheses(string s) {
            stack<int> ss;
            int start = -1;
            int size=s.size();
            int m=0;
            for(int i=0;i<size;++i)
            {
                if(s[i]=='(')//left push
                {
                    ss.push(i);
                }
                else
                {
                    if(ss.empty())
                    {
                        start=i;
                    }
                    else
                    {
                        ss.pop();
                        if(ss.empty())
                        {
                            m=max(i-start,m);
                        }
                        else
                        {
                            m=max(m,i-ss.top());
                        }
                    }
                }
            }
            return m;
        }
    };

--------------------