如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 32. 最长有效括号 这个真的难

力扣原题链接(点我直达) (opens new window)

https://mp.weixin.qq.com/s/ONRJviXVqmKimchyZLeJjg

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

示例 1:

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

示例 2:

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

# 第一版,自己写的,完全错误,没有意识到这是个DP问题

"()(()"

4

2

    int longestValidParentheses(string s) {
    stack<char> res;
	int cut = 0;
	for (auto& a : s) {
		if (res.empty() || a == '(') res.push(a);
		else if (a == ')') {
			if (res.top() == '(') {
				cut++;
				res.pop();
			}
		}


	}

	return 2 * cut;
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我这样的算法相当于计算s中有多少个匹配的括号,并没有想到序列问题

# 第二种栈的解法,其实更慢一点了

执行用时 :12 ms, 在所有 cpp 提交中击败了40.53%的用户

内存消耗 :11.7 MB, 在所有 cpp 提交中击败了5.54%的用户

对于这种括号匹配问题,一般都是使用栈

我们先找到所有可以匹配的索引号,然后找出最长连续数列!

例如:s = )(()()),我们用栈可以找到,

位置 2 和位置 3 匹配,

位置 4 和位置 5 匹配,

位置 1 和位置 6 匹配,

这个数组为:2,3,4,5,1,6 这是通过栈找到的,我们按递增排序!1,2,3,4,5,6

找出该数组的最长连续数列的长度就是最长有效括号长度!

所以时间复杂度来自排序:O(nlogn)

int longestValidParentheses(string s) { //   ())(())

	stack<int> res;
	vector<int> num;
	int len = s.size(),maxNum=0;
	for (int i = 0; i < len; ++i) {
		
		if (s[i] == '(') {
			//下标入栈
			res.push(i);
		}
		else {		
			// 出栈
			if (res.empty()) {
				res.push(i);
			}
			else if(s[res.top()]=='('){ //这一步很重要
				num.push_back(res.top());
				res.pop();
				num.push_back(i);
			}
		}
	}
	
	//for (auto& a : num) {
	//	cout << a<<endl;
	//}

	sort(num.begin(), num.end());

	//for (auto& a : num) {
	//	cout << a << endl;
	//}

	stack<int>().swap(res);
	for (auto& a : num) {
		if (res.empty())
			res.push(a);
		else if (a - res.top() == 1) {
			res.push(a);
		}
		else {

			maxNum = max(maxNum, static_cast<int>(res.size()));
			stack<int>().swap(res);
			res.push(a);
		}
	}
	maxNum = max(maxNum, static_cast<int>(res.size()));

	return maxNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 第三版本,用变量代替栈的一个解法

用变量来代替栈来优化,不过这个时候我们需要两个变量,我们假设变量为 left 和 right。

我们在从从左到右遍历字符串的过程中,用 left 记录 '(' 的数量,用 right 记录 ')' 的数量。并且在遍历的过程中:

1、如果 left >= right,显然这个时候 right 个 ')' 都将一定能够得到匹配。所以当前的有效括号长度为 2 * right。然后更新 max。

2、如果 left < right,显然这个时候部分 ')' 一定得不到匹配,此时我们把 left 和 right 都置为 0。

**当遍历完字符串,我们是否就得到最大长度的有效括号了呢?**大家可以想一下

答是不可以的,我们还需要从右到左遍历计算一下。

为什么呢?

因为实际上 '(' 和 ')' 其实是等价的,为什么就不可以倒过来遍历计算呢?所以,千万别忽略了哈。

执行用时 :4 ms, 在所有 cpp 提交中击败了96.32%的用户

内存消耗 :9 MB, 在所有 cpp 提交中击败了98.50%的用户

int longestValidParentheses(string s) { //   ())(())

	int left = 0, right = 0, maxNum = 0;
	// 从左到右
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '(') {
			left++;
		}
		else {
			right++;
		}
		if (left == right) {
			maxNum = max(maxNum, 2 * right);
		}
		else if (right > left) {
			left = right = 0;
		}
	}
	left = right = 0;
	// 从右到左
	for (int i = s.length() - 1; i >= 0; i--) {
		if (s[i] == '(') {
			left++;
		}
		else {
			right++;
		}
		if (left == right) {
			maxNum =max(maxNum, 2 * left);
		}
		else if (left > right) {
			left = right = 0;
		}
	}
	return maxNum;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

这个问题可以通过动态规划解决。我们定义一个 \text{dp}dp 数组,其中第 ii 个元素表示以下标为 ii 的字符结尾的最长有效子字符串的长度。我们将 \text{dp}dp 数组全部初始化为 0 。现在,很明显有效的子字符串一定以 \text{‘)’}‘)’ 结尾。这进一步可以得出结论:以 \text{‘(’}‘(’ 结尾的子字符串对应的 \text{dp}dp 数组位置上的值必定为 0 。所以说我们只需要更新 \text{‘)’}‘)’ 在 \text{dp}dp 数组中对应位置的值。