Leetcode趣题分享——最长有效括号

小鸡
阅读268 喜欢1 随想 更新2019-7-3

题目描述

给定一个只包含 ( ) 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-valid-parentheses

分析

一般我们做有效括号匹配,用一个栈便可以知道一个括号串是否有效匹配,但是这里的题目要求是求出括号串中最长的括号,这就不能简单地只用栈来做了,但还是需要用到栈的。

我的方法是一遍扫描,使用栈来判断之前的括号是否都匹配,如果不匹配,栈清空,技术器清零,重新开始匹配。

当然,栈清空之前,需要做下判断:栈中是否有多余的左括号,如果有,说明在这个左括号右部和左部匹配成功的括号串是分开的,并不是一个可以连接起来的有效括号串,同理,如果栈中有多个多余的左括号,那么我们需要对已经匹配好的括号串做多段切割。

例如:

(())()()

该括号串中的橙色括号是错误的匹配,但是它的左右两侧的括号都可以进行匹配,所以当程序一直匹配到括号串末尾时,都是可以正常进行的,匹配结束后我们发现多了一个左括号,所以我们需要记录括号位置,并对计数器进行数值切割。

完整代码如下

执行用时 :8 ms, 在所有 C++ 提交中击败了92.45%的用户
内存消耗 :9.4 MB, 在所有 C++ 提交中击败了90.27%的用户
class Solution {
public:
int longestValidParentheses(string s) {
if (s.length() == 0) return 0;
vector<int> ss;
int max = 0,tmp = 0, index = 1;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ")") {
if(!ss.empty()){
ss.pop_back();
tmp++;
}
else {
if (max < tmp) max = tmp;
tmp = 0;
index = 1;
ss.clear();
}
}
else {
ss.push_back(index);
index++;
}
}
if (!ss.empty()){
int mtmp = ss[0]-1;
for (int j = 1; j < ss.size(); j++)
mtmp = mtmp > ss[j]-ss[j-1]-1 ? mtmp : ss[j]-ss[j-1]-1;
tmp = mtmp > index - ss.back()-1 ? mtmp : index - ss.back()-1;
}
max = max > tmp ? max : tmp;
return max*2;
}
};