国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > LeetCode:Longest Valid Parentheses

LeetCode:Longest Valid Parentheses

来源:程序员人生   发布时间:2016-06-03 13:36:07 阅读次数:897次

Longest Valid Parentheses




Total Accepted: 63715 Total Submissions: 282480 Difficulty: Hard

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.

Subscribe to see which companies asked this question

Hide Tags
 Dynamic Programming String
Hide Similar Problems
 (E) Valid Parentheses


















思路:

使用stack来保存未匹配的“括号”的下标,然后求下标之间的最大差值。


c++ code:

class Solution { public: int longestValidParentheses(string s) { int n = s.length(); stack<int> st; for (int i = 0; i < n; i++) { if (s[i] == '(') st.push(i); else { if (!st.empty()) { if (s[st.top()] == '(') st.pop(); else st.push(i); } else st.push(i); } } int a = n, b = 0; int ans = 0; while(!st.empty()) { b = st.top(); st.pop(); ans = max(ans, a-b⑴); a = b; } ans = max(ans, a); return ans; } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生