leetcode 32. Longest Valid Parentheses 最长有效括号长度

旧城等待， 2022-06-09 09:41 111阅读 0赞

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

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

这个题的意思就是寻找最长的括号配对的长度，并返回length。基本的想法就是用栈来实现。从字符串的第一个位置开始读起，遇到左括号的话就入栈，遇到右括号的话就将栈顶元素弹出，并且判断当前序列的最长长度。栈里保存的是左括号的位置。  
具体遇到右括号时，有如下几种情况需要考虑：

1.  当前栈内无元素，则用start变量记录当前右括号的位置，表明下次比较从该右括号下一个位置开始判断；
2.  当前栈内有元素，则将栈顶元素弹出。如果弹出后的栈为空，则表明当前括号匹配，这时计算出当前的最长序列长度，即当前位置的值减去start的值即是；
3.  当前栈内又元素且弹出后的栈内仍然有元素，则最长序列长度为当前元素位置减去栈顶元素的位置。

本算法仅需要扫描一遍字符串，所以时间复杂度为O(n)，主要参考了这个链接：[http://www.cnblogs.com/zihaowang/p/4934485.html][http_www.cnblogs.com_zihaowang_p_4934485.html]

建议和[leetcode 20. Valid Parentheses][] 和 [leetcode 678. Valid Parenthesis String 有效括号的判断][leetcode 678. Valid Parenthesis String] 一起学习

同时使用类似的做法的还有这一道题，[leetcode 84. Largest Rectangle in Histogram 最大直方图][leetcode 84. Largest Rectangle in Histogram] 和[leetcode 85. Maximal Rectangle 最大子矩阵][leetcode 85. Maximal Rectangle]一定要一起学习

建议和[leetcode 301. Remove Invalid Parentheses BFS遍历得到所有合法的括号字符串 + 很棒的做法][leetcode 301. Remove Invalid Parentheses BFS_ _] 一起学习

代码如下：

import java.util.Stack;
    
    public class Solution 
    {
        /*
         * 这道题的思想就是使用栈遍历一次思想对打有效括号的匹配。
         * 从字符串的第一个位置开始读起，遇到左括号的话就入栈，遇到右括号的话就将栈顶元素弹出，并且判断当前序列的最长长度。
         * 栈里保存的是左括号的位置。
         * 
         * 具体遇到右括号时，有如下几种情况需要考虑：
         * 1. 当前栈内无元素，则用start变量记录当前右括号的位置，
         * 表明下次比较从该右括号下一个位置开始判断；
         * 
         * 2. 当前栈内有元素，则将栈顶元素弹出。如果弹出后的栈为空，
         * 则表明当前括号匹配，这时计算出当前的最长序列长度，即当前位置的值减去start的值即是；
         * 
         * 3. 当前栈内又元素且弹出后的栈内仍然有元素，
         * 则最长序列长度为当前元素位置减去栈顶元素的位置。
         * 
         * 本算法仅需要扫描一遍字符串，所以时间复杂度为O(n)；
         * 
         * */
        public int longestValidParentheses(String s) 
        {
            if(s==null || s.length()<=0)
                return 0;
    
            int beginIndex=0,maxLen=0;
            Stack<Integer> stack=new Stack<>();
            for(int i=0;i<s.length();i++)
            {
                //遇到 （ 均压入栈，压入的是index
                if(s.charAt(i)=='(')
                    stack.push(i);
                else  //  ')'
                {
                    //遇到空，说明当前无法构成合理的括号配对
                    if(stack.isEmpty())
                        beginIndex=i+1;
                    else
                    {
                        stack.pop();
                        if(stack.isEmpty())
                            maxLen=Math.max(maxLen, i-beginIndex+1);
                        else
                            maxLen=Math.max(maxLen, i-(stack.peek()+1)+1);
                    }
                }
            }
            return maxLen;
        }
    
    }

下面是C++的做法，

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <stack>
    #include <algorithm>
    using namespace std;
    
    class Solution 
    {
    public:
        int longestValidParentheses(string s) 
        {
            if (s.length() <= 1)
                return 0;
    
            int beginIndex = 0, maxLen = 0;
            stack<int> stk;
            for (int i = 0; i < s.length(); i++)
            {
                if (s[i] == '(')
                    stk.push(i);
                else
                {
                    if (stk.empty())
                        beginIndex = i + 1;
                    else
                    {
                        stk.pop();
                        if (stk.empty())
                            maxLen = max(maxLen, i - beginIndex + 1);
                        else
                            maxLen = max(maxLen, i - (stk.top() + 1) + 1);
                    }
                }
            }
            return maxLen;
        }
    };

[http_www.cnblogs.com_zihaowang_p_4934485.html]: http://www.cnblogs.com/zihaowang/p/4934485.html
[leetcode 20. Valid Parentheses]: http://blog.csdn.net/jackzhang_123/article/details/77748997
[leetcode 678. Valid Parenthesis String]: http://blog.csdn.net/jackzhang_123/article/details/78879862
[leetcode 84. Largest Rectangle in Histogram]: http://blog.csdn.net/jackzhang_123/article/details/77942100
[leetcode 85. Maximal Rectangle]: http://blog.csdn.net/jackzhang_123/article/details/77942278
[leetcode 301. Remove Invalid Parentheses BFS_ _]: http://blog.csdn.net/jackzhang_123/article/details/78131334