LeetCode:Longest Valid Parentheses

发布时间：2020-12-13 21:06:20 所属栏目：PHP教程来源：网络整理

导读：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 lo

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; } };

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!