leeyupeng

leeyupeng@126.com

0%

leetcode.32.最长有效括号

发表于 更新于 分类于 ， 阅读次数： Valine：

最长有效括号

问题描述

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

示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

示例 2:
输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

栈

思路分析

求以i为始点的最大有效括号
遇(入栈，遇)出栈
求出以0-n为始点的每一个最大有效括号，取其中最长的

超出时间限制

代码实现

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
class Solution {
public:
	int longestValidParentheses(string s)
	{
		int ans = 0;
		int n = s.length();
		int index;
		stack<bool> sta;
		for (int i = 0; i < n; i++)
		{
			index = i;
			while (index < n)
			{
				if (s[index] == '(')
				{
					sta.push(true);
				}
				else
				{
					if (sta.empty())
					{
						break;
					}
					else
					{
						sta.pop();


					}
				}
				index++;
				if (sta.empty())
				{
					ans = max(ans, index - i);
				}
			}
			if (sta.empty())
			{
			}
			else
			{
				while (!sta.empty())
				{
					sta.pop();
				}
			}
		}

		return ans;
	}
};

栈

思路分析

遇(入栈，遇)出栈，出栈时更新

  • 1.出栈后，栈为空，ans = max(ans, index - startindex + 1)
  • 2.出站后，栈不为空，max(ans, index - sta.top())

执行用时 :16 ms, 在所有 C++ 提交中击败了13.58%的用户
内存消耗 :7.2 MB, 在所有 C++ 提交中击败了100.00%的用户

代码实现

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
class Solution {
public:
	int longestValidParentheses(string s)
	{
		int ans = 0;
		int n = s.length();
		int index = 0;
		int startindex = 0;
		int top;
		stack<int> sta;

		while (index < n)
		{
			if (s[index] == '(')
			{
				sta.push(index);
			}
			else
			{
				if (sta.empty())
				{
					startindex = index + 1;
				}
				else
				{
					top = sta.top();
					sta.pop();
					if (sta.empty())
					{
						ans = max(ans, index - startindex + 1);
					}
					else
					{
						ans = max(ans, index - sta.top());
					}

				}
			}
			index++;
		}

		return ans;
	}
};

栈

思路分析

满足条件 (s[index] == ‘)’ && top>0 && s[sta[top]] == ‘(‘)出栈，否则入栈。
栈中的最大区间即ans，注意临界

代码实现

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
class Solution {
public:
	int longestValidParentheses(string s)
	{
		int ans = 0;
		int n = s.length();
		int startindex = 0;
		vector<int> sta(n + 2);
		sta[0] = -1;
		int top = 0;
		for(int index =0;index < n;index++)
		{
			if (s[index] == ')' && top>0 && s[sta[top]] == '(')
			{
				--top;
			}
			else
			{
				sta[++top] = index;
			}
		}
		sta[++top] = n;
		for (int i = 0; i < top; i++)
		{
			ans = max(ans,sta[i+1]- sta[i] - 1);
		}
		return ans;
	}
};

动态规划

思路分析

我们定义一个 dp 数组，其中第 i 个元素表示以下标为 i 的字符结尾的最长有效子字符串的长度。

转移方程：

  • 1.s[i]=‘)’ 且 s[i−1]=‘(’ ，也就是字符串形如”……()”
    dp[i]=dp[i−2]+2
  • 2.s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “…….))”
    如果s[i−dp[i−1]−1]=‘(’,那么dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

代码实现

1
2


计数器

思路分析

在这种方法中，我们利用两个计数器 leftleft 和 rightright 。首先，我们从左到右遍历字符串，对于遇到的每个 ‘(’，我们增加 left 计算器，对于遇到的每个 ‘)’ ，我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。如果 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0.

接下来，我们从右到左做一遍类似的工作。

简直奇思妙想
从左到右如果（左括号多的话，从右到左）右括号肯定少
从左到右如果（左括号少的话，从右到左）右括号肯定多

代码实现

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
class Solution {
public:
	int longestValidParentheses(string s)
	{
		int ans = 0;
		int n = s.length();
		int left = 0, right = 0;
		for (int i = 0; i < n; i++)
		{
			if (s[i] == '(') { left++; }
			else {
				right++;
				if (left == right) { ans = max(ans, left + right); }
				else if (left < right) { left = 0; right = 0; }
			}
		}
		left = 0; right = 0;
		for (int i = n - 1; i >= 0; i--)
		{
			if (s[i] == ')') { right++; }
			else {
				left++;
				if (left == right) { ans = max(ans, left + left);  }
				else if (right < left) { left = 0; right = 0; }
			}
		}
		return ans;
	}
};