32. Longest Valid Parentheses

1.問題

2.想法

• 提問

  • 如果不連續的()括號對, 是否可以累積?

• function header, parameter

• test input

• 說明想法

  • 依題意是如果括號對不連續, 則必須重新計算長度

  • 因此除了用stack儲存()外, 必須用stack儲存()在字串中的位置

    • 當()()時, ()(會先被pop, 剩下___), 長度等同於3 - (-1) =4

    • 當())()時,()會先被pop, 剩下__)_),長度等同於4 - 2 =2

    • 每一次計算新的window長度時, 與先前的相比取最大值

• 測試計算複雜度: O(n)

3.程式碼

class Solution {
public:
    int longestValidParentheses(string str) {
        int window = 0;
        stack<char> ss;
        stack<int> num;
        num.push(-1);
        int size = str.size();
        for (int i =0; i < size; i++) {
            if (str[i] == '(') {
                ss.push('(');
                num.push(i);
            } else {
                if (ss.empty() || ss.top() == ')'){
                    ss.push(')');
                    num.push(i);
                } else {
                    ss.pop();
                    num.pop();
                    window = max(window, i - num.top());
                }
            }
        }
        return window;
    }
};