## [Leetcode]32. Longest Valid Parentheses(C++)

### 题目描述

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

### 例子

#### 例子 1

Input: `"(()"` Output: 2 Explanation: The longest valid parentheses substring is `"()"`

#### 例子 2

Input: `")()())"` Output: 4 Explanation: The longest valid parentheses substring is `"()()"`

### 解题思路

• 遇到 `(`：压入栈中
• 遇到 `)`：判断当前栈是否为空：
• 栈为空：当前下标不合法，更新 `start`
• 栈不为空，表示当前右括号可以匹配，先将最近一个左括号推出，然后更新结果，通过判断栈是否为空：
• 栈为空：我们则利用 `start` 来更新：`maxLen = max(maxLen, i - start + 1)`
• 否则我们利用栈顶下标更新：`maxLen = max(maxLen, i - index.top())`

``````#include <string>
#include <stack>

class Solution {
public:
int longestValidParentheses(std::string s) {
std::stack<int> index;
int start = 0;
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
index.push(i);  // need to find a match otherwise invalid
}
else {
if (!index.empty()) {
index.pop();
maxLen = index.empty() ? std::max(maxLen, i - start + 1) : std::max(maxLen, i - index.top());
} else {
start = i + 1;      // update new valid begin pos
}
}
}
return maxLen;
}
};
``````
• 时间复杂度: O(n)
• 空间复杂度: O(n)

GitHub 代码同步地址： 32.LongestValidParentheses.cpp

Built with Hugo
Theme Stack designed by Jimmy