题1：
20. 有效的括号labuladong 题解思路
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104-
s仅由括号'()[]{}'组成
1 class Solution {
2 public boolean isValid(String s) {
3 Stack<Character> stack=new Stack<>();
4 for (int i=0;i<s.length();i++){
5 char t=s.charAt(i);
6 if (t=='('||t=='['||t=='{') stack.push(t);
7 else {
8 if (stack.isEmpty()) return false;
9 if (t==')'&&stack.peek()!='(') return false;
10 if (t==']'&&stack.peek()!='[') return false;
11 if (t=='}'&&stack.peek()!='{') return false;
12 stack.pop();
13 continue;
14 }
15 }
16 if (stack.isEmpty()) return true;
17 else return false;
18 }
19 }
括号题目通用思想，用栈判断括号成对，左括号压栈，右括号满足条件则让左括号出栈，否则就非法。
题2：
921. 使括号有效的最少添加
给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成
AB（A与B连接）, 其中A和B都是有效字符串，或者 - 它可以被写作
(A)，其中A是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())" 输出：1
示例 2：
输入："((("
输出：3
示例 3：
输入："()" 输出：0
示例 4：
输入："()))(("
输出：4
提示：
S.length <= 1000-
S只包含'('和')'字符。
1 class Solution {
2 public int minAddToMakeValid(String s) {
3 Stack<Character> stack=new Stack<>();
4 int ans=0;
5 for (int i=0;i<s.length();i++) {
6 if (s.charAt(i)=='(') stack.push(s.charAt(i));
7 else {
8 if (stack.isEmpty()) ans++;
9 else stack.pop();
10 }
11 }
12 return ans+stack.size();
13 }
14 }
同样利用栈，在不满足要求时，括号数+1，注意最后栈可能不为空，需要加上剩下的左括号数量。
也可以不利用栈，直接用left记录。
1 class Solution {
2 public int minAddToMakeValid(String s) {
3 int left=0,ans=0;
4 for (int i=0;i<s.length();i++) {
5 if (s.charAt(i)=='(') left++;
6 else {
7 if (left==0) ans++;
8 else left--;
9 }
10 }
11 return ans+left;
12 }
13 }
题3:
1541. 平衡括号字符串的最少插入次数labuladong 题解思路
难度中等给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
- 任何左括号
'('必须对应两个连续的右括号'))'。 - 左括号
'('必须在对应的连续两个右括号'))'之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
输入：s = "(()))" 输出：1 解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：
输入：s = "())" 输出：0 解释：字符串已经平衡了。
示例 3：
输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：
输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：
输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
提示：
1 <= s.length <= 10^5-
s只包含'('和')'。
1 class Solution {
2 public int minInsertions(String s) {
3 int need=0,ans=0;
4 for (int i=0;i<s.length();i++){
5 if (s.charAt(i)=='(') {
6 need+=2;
7 if (need%2==1){
8 ans++;
9 need--;
10 }
11 }
12 else {
13 need--;
14 if (need==-1){
15 ans++;
16 need=1;
17 }
18 }
19 }
20 return ans+need;
21 }
22 }
思路：用need维护需要右括号的数量。当前字符为左括号时，右括号need增加2，若need此时为奇数，则需要增加了一个右括号，即res++，need--。同理，如果为右括号，need--，此时如果need变为负数，说明右括号太多了，此时增加左括号，同时右括号need变为1。