1.判断括号合法性（栈）

输入一个字符串，其中包含{}六种括号，请你判断这个字符串组成的括号是否合法。

  1. bool isValid(string str) {
  2.     stack<Charavter> stack = new Stack<>();
  3.     for (char c : str.toCharArray()) {
  4.         if (c == '(' || c == '{' || c == '[')
  5.             left.push(c);
  6.         else { // 字符 c 是右括号
  7.             if (!left.empty() && leftOf(c) == left.peek())
  8.                 left.pop();
  9.             else
  10.                 return false; // 和最近的左括号不匹配
  11.         }
  12.     }
  13.     // 是否所有的左括号都被匹配了
  14.     return left.empty();
  15. }
  17. char leftOf(char c) {
  18.     if (c == '}') return '{';
  19.     if (c == ')') return '(';
  20.     return '[';
  21. }

2.平衡括号字符串的最少插入次数

给定一个由 ‘(‘ 和 ‘)’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(‘ 或是 ‘)’，可以在任何位置），以使得到的括号字符串有效。 leetcode 921

通过一个need变量记录对右括号的需求数，根据need的变化来判断是否需要插入

  1. 遇到左括号，need++
  2. 遇到右括号，need—

  3. 当右括号比左括号还要多need == -1 时：need清零，需插入一个左括号 res++ ```java int minAddToMakeValid(string s) { // 1 个左括号需要匹配 1 个右括号 // 1 个左括号需要匹配 2 个右括号 int res = 0; // res 记录插入左括号次数 int res = 0; int need = 0; // need 变量记录右括号的需求量 int need = 0;

    for (int i = 0; i < s.size(); i++) { for (int i = 0; i < s.size(); i++) {

     if (s[i] == '(') {                             if (s[i] == '(') {
     need++; // 对右括号的需求 + 1                   need += 2;// 一个左括号对应两个右括号
 }                                                  if (need % 2 == 1) {
 if (s[i] == ')') {                                     res++;
     need--;// 对右括号的需求 - 1                        need--;
     if (need == -1) {                               }
         need = 0; // 归零                      }
         res++;// 需插入一个左括号               if (s[i] == ')') {
     }                                             need--;
 }                                                 if (need == -1) {//右括号多1个

    } res++;// 需要插入一个左括号 return res + need; need = 1;// 对右括号的需求变为 1 } }

                                                     } 
                                             }
                                            return res + need;

<a name="wvjvl"></a>
### 3.最长有效括号

---

> 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 [**leetcode 32**](https://leetcode-cn.com/problems/longest-valid-parentheses/)

![image.png](https://cdn.nlark.com/yuque/0/2021/png/21765551/1629031945693-8af004f7-925c-4bdb-990d-ac2a3d66db3a.png#clientId=ucf4c6b5f-6395-4&from=paste&height=184&id=uc83b6bc3&margin=%5Bobject%20Object%5D&name=image.png&originHeight=367&originWidth=1527&originalType=binary&ratio=1&size=126492&status=done&style=none&taskId=u9a831b68-0083-459d-9ce6-621165be6fd&width=763.5)
<a name="iIx5I"></a>
#### 总体思路：利用栈存储下标，方便计算有效括号子串长度。

1. 首先将 -1 入栈垫底，充当参照物
1. 当字符为'('，直接将下标入栈
1. 当字符为')'，弹出栈顶元素，**若此时栈不为空，说明配对成功**，然后用')'下标减去此时栈顶元素下标即为当前有效括号子串长度；若此时栈为空，说明未配对成功，直接**将')'下标入栈垫底充当参照物**。
```java
public int longestValidParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);

        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')'){
                stack.pop();

                // ) 配对成功
                if (!stack.isEmpty()) {
                    maxLen = Math.max(maxLen, i - stack.peek());
                // ) 配对失败
                } else {
                    stack.push(i);
                }
            }
        }
        return maxLen;
    }