DP：最长有效括号

Love The Way You Lie 2023-10-06 16:51 65阅读 0赞

## DP：最长有效括号 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210315152948366.png]

#### 思路1：DP（ 时间：O（n）;空间：O(n )） ####

设DP\[i\]表示以下标i的半括号结尾的最长有效括号长度。设s为字符串，s\[i\]只能为)才能结尾，否则DP\[i\]=0。  
  当s\[i\]=)且s\[i-1\]=(时，dp\[i\]=dp\[i-2\]+2。  
  当s\[i\]=)且s\[i-1\]=)时，则在前面必有一个(与s\[i\]对应，它的位置在s\[ i-1-DP\[i-1\] \]。因此当s\[i\]=)且s\[i-1\]=)且s\[ i-1-DP\[i-1\] \]=(时：  
  DP\[i\]=DP\[i-1\]+2+DP\[ i-1-DP\[i-1\]-1 \]  
  需注意最后一项，它表示将与s\[i\]对应的左括号之前已存在的有效括号加上  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]  
  初始时将DP数组初始化为0，需注意前两个字符的特殊情况，当s\[0\]=(且s\[1\]=)时，需将dp\[1\]设为2，否则dp\[1\]在之后的循环中不会更新

#### 代码： ####

class Solution {
        
    public:
        int longestValidParentheses(string s) {
        
            int n=s.size();
            int i;
            int* dp;
            dp=( int* )malloc( n*sizeof( int ) );
            if( s.size()<=1 )
                return 0;
            int maxx=0; 
            for( i=0;i<n;i++ )
                dp[i]=0;  
            if( s[0]=='(' && s[1]==')' )
            {
        
                dp[1]=2;
                maxx=max( maxx,dp[1] );
            }   
            for( i=0;i<n;i++ )
            {
        
                if( i-1>=0 && s[i]==')' && s[i-1]=='(' )
                {
        
                    if( i-2>=0 )
                    {
        
                        dp[i]=dp[i-2]+2;
                        maxx=max( maxx,dp[i] );
                    }
                }
                else if( i-1>=0 && s[i]==')' && s[i-1]==')' )
                {
        
                    if( i-dp[i-1]-1>=0 && s[ i-dp[i-1]-1 ]=='(' )
                    {
           
                        dp[i]=dp[i-1]+2;
                        if( i-dp[i-1]-2>=0 )
                            dp[i]+=dp[ i-dp[i-1]-2 ];
                        maxx=max( maxx,dp[i] );
                    }
                }
            }
            return maxx;
        }
    };

#### 思路2：栈（ 时间：O（n）;空间：O(n )） ####

由于只需求最长有效括号串的长度，因此我们只需将下标入栈。我们的想法是：每遇到左括号，将其入栈，每遇到右括号，将栈顶左括号出栈，根据它的下标计算有效括号串长度，即当前下标-出栈元素下标+1  
  考虑以下情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]  
  我们会发现一个问题：遍历到下标为5的元素时，计算出的长度为5-2+1=4，最前面的两个元素不在栈中，被忽略掉了；

我们需要最前面的括号串留下它的痕迹，为此我们需要修改计算有效括号串长度的规则，我们需要将每个有效括号串前面的一个字符作为标识压入栈中

我们引入垫底下标解决该问题，在初始栈时将-1 push进去，计算长度的规则变为：当前下标-出栈后的栈顶元素下标。

垫底下标是需要更换的，当栈中只有一个元素，即垫底元素时，若当前遍历到的为)，如下标为6的元素，表示前面的有效字符串已结束，此时将当前下标作为垫底元素压入栈中

#### 代码： ####

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

#### 思路3：双向扫描记录左右括号个数（ 时间：O（n）;空间：O(1) ） ####

对于每个有效括号串，其左括号个数一定等于右括号个数。 我们用left记录左括号个数，用right记录右括号个数，从左到右遍历字符串，若右括号个数已经大于左括号个数，则不可能构成有效括号串，将left和right赋为0。若left==right，则更新最长括号串长度

但这样我们会发现一个问题，若左括号数大于右括号数，但已经不可能成为有效括号串的情况，如(()，我们从左到右遍历时会认为它仍有可能成为有效括号，因此无法排除这种情况

因此我们再进行反向遍历解决该问题，不过反向遍历时，若左括号数已经大于右括号数，将left和right重置为0

#### 代码： ####

class Solution {
        
    public:
        int longestValidParentheses(string s) {
        
            int left=0;
            int right=0;
            int i;
            int maxx=0;
            int n=s.size();
            for( i=0;i<n;i++ )
            {
        
                if( s[i]=='(' )
                {
        
                    left++;
                }
                else
                {
        
                    right++;
                }
                if( left<right )
                {
           
                    left=0;
                    right=0;
                }
                else if( left==right )
                {
        
                    maxx=max( left+right,maxx );
                }
            }
            left=0;
            right=0;
            for( i=n-1;i>=0;i-- )
            {
        
                if( s[i]=='(' )
                {
        
                    left++;
                }
                else
                {
        
                    right++;
                }
                if( left>right )
                {
           
                    left=0;
                    right=0;
                }
                else if( left==right )
                {
        
                    maxx=max( left+right,maxx );
                }
            }
            return maxx;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210315152938429.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20210315152948366.png]: https://img-blog.csdnimg.cn/20210315152948366.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210315154323409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210315161802601.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70