【问题描写叙述】
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.
1.【基础知识】
压栈、弹栈机制可以非常好的模仿括号配对。
2.【屌丝代码】
- 完毕失败。
- 达成思想：
- 卡壳部分
3.【AC源代码】
// LeetCode, Longest Valid Parenthese
// 使用栈，时间复杂度 O(n)。空间复杂度 O(n)
class Solution {
public:
int longestValidParentheses(string s) {
int max_len = 0, last = -1; // the position of the last ')'
stack<int> lefts; // keep track of the positions of non-matching '('s
for (int i = 0; i < s.size(); ++i) { if (s[i] =='(')
{
lefts.push(i);
}
else
{
if (lefts.empty())
{
// no matching left
last = i;
}
else
{
// find a matching pair
lefts.pop();
if (lefts.empty())
{
max_len = max_len>=i-last?max_len:i-last;
}
else
{
// lefts.top() 表示上一个未匹配的正括号
// i-lefts.top() 表示已匹配括号长度
max_len = max_len>=i-lefts.top()?max_len:i-lefts.top();
}
}
}
}
return max_len;
}
};
4.【复盘】
5.【算法核心思想】