首页 > 代码库 > Longest Valid Parentheses
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.
思路：使用vector模拟栈，栈顶元素表示出现在当前‘(’之后的合法匹配数，栈本身具有一个哨位节点。依次遍历s，若当前字符s[i]==‘(‘，则将0入栈；否则，将栈顶元素加2后再加到次栈顶元素，同时栈顶元素出栈。
1 class Solution { 2 public: 3 int longestValidParentheses( string s ) { 4 int slen = s.length(), idx = 0, ret = 0; 5 if( slen <= 1 ) { return 0; } 6 vector<int> cntVec( slen+1, 0 ); 7 for( int i = 0; i < slen; ++i ) { 8 if( s[i] == ‘(‘ ) { 9 cntVec[++idx] = 0;10 } else {11 if( idx > 0 ) {12 cntVec[idx-1] += cntVec[idx]+2;13 ret = max( ret, cntVec[--idx] );14 } else {15 cntVec[0] = 0;16 }17 }18 }19 return ret;20 }21 };
Longest Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。