关于括号匹配的最小交换数-----数学(所有右括号的数量大于左括号时才需调整)

注意括号的题目，左边直接无脑压栈，遇到右括号再判断

思路

每到一个位置，只要我们左括号的个数不少于右括号的个数，它就是平衡的。否则必须进行交换

5840. 使字符串平衡的最小交换次数

分析

当循环s[i]点时，所有右括号的数量大于左括号时，才需要调整。

知道了这点就可以轻松解题了！

1. 循环字符串s

2. 记录左括号l和有括号r的大小

3. 当s[i]为左括号，l无脑+1

4. 当s[i]为右括号，需要判断当前r是否大于等于l，

   • 如果r > l: 那么l+1,同时交换数 + 1
   • 否则r+1
5. 最终返回交换数

class Solution {
    public int minSwaps(String s) {
        int l = 0;
        int r = 0;
        int ret = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '[') {
                l++;
            } else {
                if (l <= r) {
                    l++;
                    ret++;
                } else {
                    r++;
                }
            }
        }
        return ret;
    }
}

最长的有效括号序列

class Solution {
    //栈
    //从左往右扫描，已扫描的左括号等待匹配，用一个栈保存
    //题目是求长度，存索引即可，没必要存左括号本身
    //遇到右括号，匹配最近一个左括号——栈顶元素出栈，有效长度 = 当前索引 - 出栈的索引 + 1，并挑战一下全局的最大

    public int longestValidParentheses(String s) {
        // 用栈解决括号的合法性问题，向栈中存入下标
        Deque<Integer>stack = new LinkedList<Integer>();
        // 向栈中预置一个-1，将计算长度的方式转化成“）”的下标减去出栈后栈顶元素的下标
        stack.push(-1);
        int len = 0;
        for (int i = 0; i < s.length(); i++) {
            if ('('==s.charAt(i)) {
                stack.push(i);
            }
            if (')'==s.charAt(i)) {
                stack.pop();
                // 如栈空，则注入新的i作为预置下标
                if (stack.isEmpty()) {
                    stack.push(i);
                }
                len = Math.max(len, i-stack.peek());

            }
        }
        return len;
    }
}