# [LeetCode]32.Longest Valid Parentheses

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

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

• 如果栈为空，用当前元素下标i 减去 last计算有效长度；
• 如果栈不为空，用当前元素下标i 减去 栈顶元素下标计算有效长度；

/*---------------------------------------------------------
*   日期：2015-04-23
*   作者：SJF0115
*   题目: 32.Longest Valid Parentheses
*   网址：https://leetcode.com/problems/longest-valid-parentheses/
*   结果：AC
*   来源：LeetCode
*   博客：
------------------------------------------------------------*/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
int longestValidParentheses(string s) {
int size = s.size();
if(size <= 1){
return 0;
}//if
int last = -1;
int Max = 0;
stack<int> leftStack;
for(int i = 0;i < size;++i){
// (入栈
if(s[i] == '('){
leftStack.push(i);
}//if
else if(s[i] == ')'){
if(leftStack.empty()){
last = i;
}//if
else{
leftStack.pop();
if(leftStack.empty()){
Max = max(Max,i - last);
}//if
else{
Max = max(Max,i - leftStack.top());
}//else
}//else
}//else
}//for
return Max;
}
};

int main(){
Solution solution;
string str("()(()");
cout<<solution.longestValidParentheses(str)<<endl;
return 0;
}


|
10月前
Leetcode 516. Longest Palindromic Subsequence

37 0
|
3月前
|

LeetCode 题目 65：有效数字（Valid Number）【python】
LeetCode 题目 65：有效数字（Valid Number）【python】
41 5
|
10月前
|
Java
Leetcode 3. Longest Substring Without Repeating Characters

41 3
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
102 0
LeetCode 424. Longest Repeating Character Replacem

97 0
LeetCode 409. Longest Palindrome

67 0
LeetCode 395. Longest Substring with At Least K

76 0
|
Windows
LeetCode 388. Longest Absolute File Path

70 0
LeetCode 367. Valid Perfect Square

89 0
|

LeetCode 329. Longest Increasing Path in a Matrix

60 0

DDNS