删除最外层的括号（Leetcode）

2020-12-30

1. 题目

https://leetcode-cn.com/problems/remove-outermost-parentheses/

https://leetcode.com/problems/remove-outermost-parentheses/

去除一个字符串里面的最外层括号，字符串只包括 ( 和 ) 这两个字符。

() => 空字符串
((())) => (())
(()()) => ()()
(()())(()) => ()()()

2. 思路

思路 1 - 利用 stack

用 stack 来存左括号，遇到右括号之后 pop 一个左括号；
pop 之后 stack 为空，就证明找到了最外层的右括号；
如当前 stack count 大于 0，说明现在处于里层，需要把这个字符存起来；

实现 1

这是第一次的实现，用了两个 stack，一个是存括号的，一个是存 character index 的。


public class Solution
{
	public string RemoveOuterParentheses(string S)
	{
		Stack<char> stack = new Stack<char>();
		Stack<int> toRemove = new Stack<int>();
		List<char> arr = S.ToCharArray().ToList();
		int start = 0;
		int end = 0;
		for (int i = 0; i < arr.Count(); i++){
			char c = arr[i];
			if (c == '('){
				if (stack.Count() == 0)
					start = i;
				stack.Push(c);
			}
			else
			{
				stack.Pop();
				if (stack.Count() == 0)
				{
					// found a primitive parenthese
					end = i;
					toRemove.Push(start);
					toRemove.Push(end);
				}
			}
		}
		while (toRemove.Count() > 0)
			arr.RemoveAt(toRemove.Pop());

		StringBuilder sb = new StringBuilder();
		sb.Append(arr.ToArray());

		return sb.ToString();
	}
}

实现 2

参考了别人的解题思路之后，发现不需要分为两步（找 index，去除 character），而是可以在遍历 char array 的时候直接根据 count 来 build string。

这个方法里面最重要的就是 foreach 里面的 if 判断顺序，我们必须先去掉右括号，再决定是否要把当前字符加入最终结果，这个判断结束之后再把左括号加进去。

为什么要用这个顺序呢？

假如当前字符是最外层的左括号，那么在这个左括号加入 stack 之前，stack count 一定等于 0；
假如当前字符是最外层的右括号，那么在 pop 之前，stack count 一定大于 0；

所以我们要先 pop，再判断 count，最后 push。


public class Solution
{
	public string RemoveOuterParentheses(string S)
	{
		StringBuilder sb = new StringBuilder();
		Stack<char> stack = new Stack<char>();
		char[] arr = S.ToCharArray();
		foreach (char c in arr)
		{
			if (c == ')')
				stack.Pop();
			if (stack.Count() > 0)
				sb.Append(c);
			if (c == '(')
				stack.Push(c);
		}

		return sb.ToString();
	}
}

思路 2. 计算剩余括号数量

这个思路比较巧妙，因为根据题意，我们可以发现左括号和右括号的数量是一样的，所以就用一个专门的变量来存左括号数量，假如左括号数量大于 0 ，加入 final string。

这个解法不需要用 stack。

值得注意的是 left++ > 0 和 --left > 0 这两个比较，第一个用的是后++，第二个用的是前–。

区别在于：

i++（后++）是先用后算，先把 i 的值用来做比较，再把 i 的值 + 1；
++i（前++）是先算后用，先把 i 的值 + 1，再使用这个新的值作比较；

也就是说，当我们输入 () 的时候，left++ > 0 会保证左括号不被加入最终结果（先用后算， 0 > 0 不成立，left = 0+1 = 1）；而 –left > 0 会保证右括号不被加入最终结果（因为先算后用，left = 1-1 = 0，0 > 0 不成立）；这样也就能保证最外层的括号不被加入最终结果了~


public class Solution
{
	public string RemoveOuterParentheses(string S)
	{
		int left = 0;
		StringBuilder sb = new StringBuilder();
		char[] arr = S.ToCharArray();
		for (int i = 0; i < arr.Count(); i++)
		{
			char c = arr[i];
			if (c == '(' && left++ > 0) // 先用后算，先和 0 比较，再加 1
			{
				sb.Append('(');
			}
			if (c == ')' && --left > 0) // 先算后用，先-1，再和 0 比较
				sb.Append(')');
		}
		return sb.ToString();
	}
}

3. 复盘

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

注意点

用 StringBuilder 来储存结果，因为 string 是 immutable type，每操作一次就创建一个新的 string，在内存方面不如 StringBuilder 友好；
在【思路 1-实现 1】里面，由于 char array 不能用 RemoveAtIndex 之类的方法来去掉不需要的括号，所以我先把 char array 转成了一个 List，然后在 StringBuilder 里面转回 array；
前++ 是先算后用，后++是先用后算

延伸阅读

简单来说：

Array 是长度固定的对象，定义之后不能改变长度，可以改变元素的值，所有元素类型一致；
ArrayList 长度不固定，可以增减元素，元素类型可以不一致；
List 介于两者之间，保证了元素类型一致，且长度可以被改变；

// Array
int[] Array = new int[5];
for(int i = 0; i < Array.Length; i++)
{
	Array[i] = i + 5;
}
Array[0] = 10;

// ArrayList
ArrayList arrayList = new ArrayList();
arrayList.Add(6);
arrayList.Add("123");
arrayList.RemoveAt(0);

// List
List<int> list = new List<int>();
list.Add(6);
list.Add(8);
list.RemoveAt(0);

结语

欢迎大家分享更好的解法~