LeetCode 32. 最长有效括号
原题链接
困难
作者:
ShineShaye
,
2022-07-06 16:09:22
,
所有人可见
,
阅读 124
合法括号序列:1,左右括号数量相等;2,任意前缀中左括号数量大于等于右括号
记录括号数量与匹配长度:
开一个栈
左括号则入栈,存储内容为其下标
右括号就检查栈是否空,不空就弹出栈顶(那么左括号少一个)
每次右括号找到一个匹配的左括号,匹配长度为这个左右括号子串的长度,max一下
关键思路:
出现左括号数量小于右括号时,该位置非法,任何有效序列不可能跨越(反证可得)
此时可以置起始位置start为该点(下一个合法序列的上一位置,故初始化为-1)
有这个start之后就可以很容易求每次匹配的序列长度:
右括号i弹出一个左括号,栈顶存储的就是匹配序列的前一个位置:
(i - stack.top())
如果弹出后栈空,说明从start开始都可以匹配
i - start
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
int start = -1, res = 0;
for(int i = 0; i < s.size();++i)
{
if(s[i] == '(') stk.push(i);
else if(!stk.empty())
{
stk.pop();
if(stk.empty()) res = max(res, i - start);
else res = max(res, i - stk.top());
}
else
start = i;
}
return res;
}
};