> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/32.-longest-valid-parentheses.md).

# 32. Longest Valid Parentheses

## 1.問題

![](/files/-LMI1dZj-TQnHi670Qn4)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 如果不連續的()括號對, 是否可以累積?&#x20;
* function header, parameter
* test input
* 說明想法
  * 依題意是如果括號對不連續, 則必須重新計算長度
  * 因此除了用stack儲存()外, 必須用stack儲存()在字串中的位置
    * 當()()時, ()(會先被pop, 剩下\_\_\_), 長度等同於3 - (-1) =4
    * 當())()時,()會先被pop, 剩下\_\_)\_),長度等同於4 - 2 =2
    * 每一次計算新的window長度時, 與先前的相比取最大值&#x20;
* 測試計算複雜度: O(n)

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
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;
    }
};
```