[C++] LeetCode 32. 最長有效括号

題目

給一個隻包含

'('

和

')'

的字元串，找出最長的有效（正确關閉）括号子串的長度。

對于

"(()"

，最長有效括号子串為

"()"

，它的長度是

2

。

另一個例子

")()())"

，最長有效括号子串為

"()()"

，它的長度是

4

。

方法一

這道題可以考慮用棧來實作，這樣一次周遊就可以OK了。假定

(

用數字

-2

表示，

)

用數字

-1

表示，正數表示現階段可以組成封閉括号的長度。

如果遇到

(

直接入棧

如果遇到

)

考慮如下幾種情況：

1、棧為空，此時直接

continue

即可

2、棧頂為

(

，則可以配對，棧彈出棧頂元素，如果此時棧頂為正數，則彈出正數加

2

重新入棧，否則直接壓入

2

3、棧頂為正數，則彈出棧頂元并記錄，此時針對棧頂元考慮步驟

1

和

2

的情況。

代碼如下

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int res=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                st.push(-2);
                continue;
            }
            if(st.empty()) continue;
            if(st.top()==-2){
                st.pop();
                if(st.empty()||st.top()<0) st.push(2);
                else{
                    int tmp=st.top()+2;
                    st.pop();
                    st.push(tmp);
                }
                res=max(res,st.top());
                continue;
            }
            if(st.top()>0){
                int tmp=st.top();
                st.pop();
                if(st.empty()) continue;
                else{
                    tmp+=2;
                    st.pop();
                    while(!st.empty()&&st.top()>0){
                        tmp+=st.top();
                        st.pop();
                    }
                    st.push(tmp);
                    res=max(res,st.top());
                }
            }

        }
        return res;
    }
};
           

方法二

這題可以用動态規劃求解，開一個數組

vector<int> count

表示以

i

位置結尾的最長有效括号子串的長度。如果

s[i]==')'

且

j=i-1-count[i-1];

• s[i-1]=='('

  ，則

  j=i-1

  ，此時考慮

  count[i]=2+count[i-2]=2+count[j-1]

• s[i-1]==')'

  ，則

  j=i-1-count[i-1]

  ，此時如果

  s[j]=='('

  ，則

  count[i]=2+count[i-1]+count[j-1]

  （例如

  s=()(())

  ）
• 綜合上述兩種情況，可以寫成

  count[i]=2+count[i-1]+count[j-1]

代碼

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.size(),res=0;
        vector<int> count(n,0);
        for(int i=1;i<n;i++){
            if(s[i]=='(') continue;
            int j=i-1-count[i-1];
            if(s[j]=='(')
                count[i]=2+count[i-1]+(j>0?count[j-1]:0);
            res=max(res,count[i]);
        }
        return res;
    }
};