---
tags: LeetCode,Top 100 Liked Questions
---
# 32. Longest Valid Parentheses
https://leetcode.com/problems/longest-valid-parentheses/
## 題目敘述
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
## Example
Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

## 解題想法
### 1 stack
利用stack紀錄座標
在s[i]='('時將座標紀錄為start
(1)在s[i]=')'時先確認stack.empty
若為空->Valid Parentheses的開頭為下一格
若為不為空->先將stack pop
(2)再確認stack.empty
為空->為Valid Parentheses先記錄length(如"()")
不為空->Valid Parentheses為i-stack.top(如"(()")

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

時間複雜度為O(N)