标签： medium

目标

给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。

在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。

返回使整个数组变为 0 所需的最少操作次数。

一个 子数组 是数组中的一段连续元素。

示例 1：

输入: nums = [0,2]
输出: 1
解释:
选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为 [0,0]。
因此，所需的最少操作次数为 1。

示例 2：

输入: nums = [3,1,2,1]
输出: 3
解释:
选择子数组 [1,3]（即 [1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为 [3,0,2,0]。
选择子数组 [2,2]（即 [2]），将 2 设为 0，结果为 [3,0,0,0]。
选择子数组 [0,0]（即 [3]），将 3 设为 0，结果为 [0,0,0,0]。
因此，最少操作次数为 3。

示例 3：

输入: nums = [1,2,1,2,1,2]
输出: 4
解释:
选择子数组 [0,5]（即 [1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为 [0,2,0,2,0,2]。
选择子数组 [1,1]（即 [2]），将 2 设为 0，结果为 [0,0,0,2,0,2]。
选择子数组 [3,3]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,2]。
选择子数组 [5,5]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,0]。
因此，最少操作次数为 4。

说明:

• 1 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5

思路

有一个非负整数数组 nums，每一次操作可以任选一个子数组，将子数组的最小非负整数设为 0，求将整个数组变为 0 所需的最小操作次数。

保存元素值与下标的映射，同时记录已经变为 0 的元素下标，按照元素值从小到大的顺序枚举对应的下标，同时判断该下标后面是否有已变为 0 的下标。

代码

/**
 * @date 2025-11-10 8:53
 */
public class MinOperations3542 {

    public int minOperations(int[] nums) {
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        TreeSet<Integer> zeros = new TreeSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int v = nums[i];
            if (v == 0) {
                zeros.add(i);
                continue;
            }
            map.putIfAbsent(v, new ArrayList<>());
            map.get(v).add(i);
        }
        int res = 0;
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            if (zeros.size() == 0) {
                res++;
                zeros.addAll(entry.getValue());
                continue;
            }
            Integer right = null;
            for (Integer index : entry.getValue()) {
                if (right != null && index < right) {
                    continue;
                }
                res++;
                right = zeros.higher(index);
                if (right == null) {
                    break;
                }
            }
            zeros.addAll(entry.getValue());
        }
        return res;
    }

}

性能

目标

给你一个整数 c，表示 c 个电站，每个电站有一个唯一标识符 id，从 1 到 c 编号。

这些电站通过 n 条 双向 电缆互相连接，表示为一个二维数组 connections，其中每个元素 connections[i] = [ui, vi] 表示电站 ui 和电站 vi 之间的连接。直接或间接连接的电站组成了一个 电网 。

最初，所有 电站均处于在线（正常运行）状态。

另给你一个二维数组 queries，其中每个查询属于以下 两种类型之一 ：

• [1, x]：请求对电站 x 进行维护检查。如果电站 x 在线，则它自行解决检查。如果电站 x 已离线，则检查由与 x 同一 电网 中 编号最小 的在线电站解决。如果该电网中 不存在 任何 在线 电站，则返回 -1。
• [2, x]：电站 x 离线（即变为非运行状态）。

返回一个整数数组，表示按照查询中出现的顺序，所有类型为 [1, x] 的查询结果。

注意：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。

示例 1：

输入： c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]
输出： [3,2,3]
解释：
最初，所有电站 {1, 2, 3, 4, 5} 都在线，并组成一个电网。
查询 [1,3]：电站 3 在线，因此维护检查由电站 3 自行解决。
查询 [2,1]：电站 1 离线。剩余在线电站为 {2, 3, 4, 5}。
查询 [1,1]：电站 1 离线，因此检查由电网中编号最小的在线电站解决，即电站 2。
查询 [2,2]：电站 2 离线。剩余在线电站为 {3, 4, 5}。
查询 [1,2]：电站 2 离线，因此检查由电网中编号最小的在线电站解决，即电站 3。

示例 2：

输入： c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]
输出： [1,-1]
解释：
没有连接，因此每个电站是一个独立的电网。
查询 [1,1]：电站 1 在线，且属于其独立电网，因此维护检查由电站 1 自行解决。
查询 [2,1]：电站 1 离线。
查询 [1,1]：电站 1 离线，且其电网中没有其他电站，因此结果为 -1。

说明：

• 1 <= c <= 10^5
• 0 <= n == connections.length <= min(10^5, c * (c - 1) / 2)
• connections[i].length == 2
• 1 <= ui, vi <= c
• ui != vi
• 1 <= queries.length <= 2 * 10^5
• queries[i].length == 2
• queries[i][0] 为 1 或 2。
• 1 <= queries[i][1] <= c

思路

有 c 个电站，编号为 1 ~ c，connections[i] = [ui, vi] 表示电站 ui 与 vi 相连，所有连通的电站组成了一个电网。查询 queries[i] = [operation, x]，如果 operation 为 2 表示将电站 x 离线，如果 operation 为 1 并且 x 在线，返回 x，否则返回 x 所在电网中在线电站的最小编号，如果没有在线电站返回 -1。

使用 有序集合 数组 维护不同电网的在线电站。如果离线就将其从有序集合中删掉 O(logn)，否则先判断集合是否为空，如果集合为空返回 -1，再判断电站是否在集合中 O(logn)，如果在则直接返回查询电站编号，否则取集合最小的编号。

代码

/**
 * @date 2025-11-06 9:03
 */
public class ProcessQueries3607 {

    private class UnionFind {
        private int[] fa;

        public UnionFind() {
        }

        public UnionFind(int n) {
            this.fa = new int[n];
            Arrays.setAll(this.fa, i -> i);
        }

        public int find(int x) {
            if (fa[x] != x) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        }

        public void merge(int x, int y) {
            int a = find(x);
            int b = find(y);
            if (a != b) {
                fa[b] = a;
            }
        }

    }

    public int[] processQueries(int c, int[][] connections, int[][] queries) {
        UnionFind uf = new UnionFind(c + 1);
        for (int[] connection : connections) {
            uf.merge(connection[0], connection[1]);
        }
        TreeSet<Integer>[] set = new TreeSet[c + 1];
        Arrays.setAll(set, i -> new TreeSet<>());
        for (int i = 1; i <= c; i++) {
            set[uf.find(i)].add(i);
        }
        List<Integer> list = new ArrayList<>();
        boolean[] off = new boolean[c + 1];
        for (int[] query : queries) {
            int operation = query[0];
            int node = query[1];
            int network = uf.find(node);
            if (operation == 1) {
                if (set[network].size() > 0) {
                    if (off[node]) {
                        list.add(set[network].first());
                    } else {
                        list.add(node);
                    }
                } else {
                    list.add(-1);
                }
            } else {
                off[node] = true;
                set[network].remove(node);
            }
        }
        return list.stream().mapToInt(i -> i).toArray();
    }
}

性能

目标

Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。

Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个 下标从 0 开始 的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。

返回 Bob 使绳子变成 彩色 需要的 最少时间 。

示例 1：

输入：colors = "abaac", neededTime = [1,2,3,4,5]
输出：3
解释：在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。
Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。

示例 2：

输入：colors = "abc", neededTime = [1,2,3]
输出：0
解释：绳子已经是彩色的，Bob 不需要从绳子上移除任何气球。

示例 3：

输入：colors = "aabaa", neededTime = [1,2,3,4,1]
输出：2
解释：Bob 会移除下标 0 和下标 4 处的气球。这两个气球各需要 1 秒来移除。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 1 + 1 = 2 。

说明：

• n == colors.length == neededTime.length
• 1 <= n <= 10^5
• 1 <= neededTime[i] <= 10^4
• colors 仅由小写英文字母组成

思路

水平的绳子上绑着一排气球，现在要使相邻的气球颜色不同，需要解开一些气球，解开每个气球的时间为 neededTime[i] 求所需的最短时间。

将相邻的颜色相同的气球放入堆中，仅保留耗时最大的即可。

代码

/**
 * @date 2025-11-03 8:56
 */
public class MinCost1578 {

    public int minCost(String colors, int[] neededTime) {
        int n = neededTime.length;
        int i = 0;
        int res = 0;
        while (i < n) {
            int max = i;
            int sum = 0;
            char c = colors.charAt(i);
            while (i < n && c == colors.charAt(i)) {
                if (neededTime[i] > neededTime[max]) {
                    max = i;
                }
                sum += neededTime[i++];
            }
            res += sum - neededTime[max];
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。

示例 1：

输入： nums = [1,2,3], head = [1,2,3,4,5]
输出： [4,5]
解释：
移除数值为 1, 2 和 3 的节点。

示例 2：

输入： nums = [1], head = [1,2,1,2,1,2]
输出： [2,2,2]
解释：
移除数值为 1 的节点。

示例 3：

输入： nums = [5], head = [1,2,3,4]
输出： [1,2,3,4]
解释：
链表中不存在值为 5 的节点。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• nums 中的所有元素都是唯一的。
• 链表中的节点数在 [1, 10^5] 的范围内。
• 1 <= Node.val <= 10^5
• 输入保证链表中至少有一个值没有在 nums 中出现过。

思路

依题意模拟即可，删除链表中的指定节点。

代码

/**
 * @date 2025-11-03 13:55
 */
public class ModifiedList3217 {

    public ListNode modifiedList_v1(int[] nums, ListNode head) {
        Set<Integer> set = new HashSet<>(nums.length, 1);
        for (int num : nums) {
            set.add(num);
        }
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (head != null) {
            if (set.contains(head.val)) {
                prev.next = head.next;
            } else {
                prev = head;
            }
            head = head.next;
        }
        return dummy.next;
    }

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

性能

目标

银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。

对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：

• 两个设备位于两个 不同行 ：r1 和 r2 ，其中 r1 < r2 。
• 满足 r1 < i < r2 的 所有 行 i ，都 没有安全设备 。

激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。

返回银行中激光束的总数量。

示例 1：

输入：bank = ["011001","000000","010100","001000"]
输出：8
解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束：
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
注意，第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备，这不满足第 2 个条件。

示例 2：

输入：bank = ["000","111","000"]
输出：0
解释：不存在两个位于不同行的设备

提示：

• m == bank.length
• n == bank[i].length
• 1 <= m, n <= 500
• bank[i][j] 为 '0' 或 '1'

思路

跳过中间的空行，将相邻的非空行上的装置数量相乘。

代码

/**
 * @date 2025-10-27 10:34
 */
public class NumberOfBeams2125 {

    public int numberOfBeams(String[] bank) {
        int prev = 0, cur = 0;
        int res = 0;
        for (String b : bank) {
            for (char c : b.toCharArray()) {
                if (c == '1') {
                    cur++;
                }
            }
            if (cur == 0) {
                continue;
            }
            res += cur * prev;
            prev = cur;
            cur = 0;
        }
        return res;
    }

}

性能

目标

你的任务是为一个很受欢迎的银行设计一款程序，以自动化执行所有传入的交易（转账，存款和取款）。银行共有 n 个账户，编号从 1 到 n 。每个账号的初始余额存储在一个下标从 0 开始的整数数组 balance 中，其中第 (i + 1) 个账户的初始余额是 balance[i] 。

请你执行所有 有效的 交易。如果满足下面全部条件，则交易 有效 ：

• 指定的账户数量在 1 和 n 之间，且
• 取款或者转账需要的钱的总数 小于或者等于 账户余额。

实现 Bank 类：

• Bank(long[] balance) 使用下标从 0 开始的整数数组 balance 初始化该对象。
• boolean transfer(int account1, int account2, long money) 从编号为 account1 的账户向编号为 account2 的账户转帐 money 美元。如果交易成功，返回 true ，否则，返回 false 。
• boolean deposit(int account, long money) 向编号为 account 的账户存款 money 美元。如果交易成功，返回 true ；否则，返回 false 。
• boolean withdraw(int account, long money) 从编号为 account 的账户取款 money 美元。如果交易成功，返回 true ；否则，返回 false 。

示例：

输入：
["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
输出：
[null, true, true, true, false, false]

解释：
Bank bank = new Bank([10, 100, 20, 50, 30]);
bank.withdraw(3, 10);    // 返回 true ，账户 3 的余额是 $20 ，所以可以取款 $10 。
                         // 账户 3 余额为 $20 - $10 = $10 。
bank.transfer(5, 1, 20); // 返回 true ，账户 5 的余额是 $30 ，所以可以转账 $20 。
                         // 账户 5 的余额为 $30 - $20 = $10 ，账户 1 的余额为 $10 + $20 = $30 。
bank.deposit(5, 20);     // 返回 true ，可以向账户 5 存款 $20 。
                         // 账户 5 的余额为 $10 + $20 = $30 。
bank.transfer(3, 4, 15); // 返回 false ，账户 3 的当前余额是 $10 。
                         // 所以无法转账 $15 。
bank.withdraw(10, 50);   // 返回 false ，交易无效，因为账户 10 并不存在。

说明：

• n == balance.length
• 1 <= n, account, account1, account2 <= 10^5
• 0 <= balance[i], money <= 10^12
• transfer, deposit, withdraw 三个函数，每个 最多调用 10^4 次

思路

依题意模拟即可。

代码

class Bank {

    private long[] balance;

    public Bank(long[] balance) {
        this.balance = balance;
    }

    public boolean transfer(int account1, int account2, long money) {
        if (account1 > balance.length || account2 > balance.length || balance[account1 - 1] < money){
            return false;
        }
        balance[account1 - 1] -= money;
        balance[account2 - 1] += money;
        return true;
    }

    public boolean deposit(int account, long money) {
        if (account > balance.length){
            return false;
        }
        balance[account - 1] += money;
        return true;
    }

    public boolean withdraw(int account, long money) {
        if (account > balance.length || balance[account - 1] < money ){
            return false;
        }
        balance[account - 1] -= money;
        return true;
    }
}

/**
 * Your Bank object will be instantiated and called as such:
 * Bank obj = new Bank(balance);
 * boolean param_1 = obj.transfer(account1,account2,money);
 * boolean param_2 = obj.deposit(account,money);
 * boolean param_3 = obj.withdraw(account,money);
 */

性能

目标

如果整数 x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。

给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。

示例 1：

输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：
- 数字 2 出现 2 次 
这也是严格大于 1 的最小数值平衡数。

示例 2：

输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。

示例 3：

输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 3000 的最小数值平衡数。

说明：

• 0 <= n <= 10^6

思路

定义平衡数中每一位上数字的出现次数 cnt[d] = d，判断大于 n 的最小平衡数。

回溯构造 10^7 范围内的所有平衡数，然后二分查找。

官网题解是枚举所有大于 n 的整数，判断是否是平衡数，也可以预处理 (n, 1224444] 范围内的所有平衡数，然后二分查找。

代码

/**
 * @date 2025-10-24 9:12
 */
public class NextBeautifulNumber2048 {

    public int nextBeautifulNumber(int n) {
        return set.higher(n);
    }

    private static final TreeSet<Integer> set = new TreeSet<>();

    static {
        int[] cnt = new int[7];
        Arrays.setAll(cnt, i -> i);
        dfs(0, 0, 7, cnt);
    }

    public static void dfs(int cur, int l, int length, int[] cnt) {
        if (l > length + 1) {
            return;
        }
        boolean balance = true;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] != i && cnt[i] != 0) {
                balance = false;
                break;
            }
        }
        if (balance) {
            set.add(cur);
        }
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            cnt[i]--;
            dfs(cur * 10 + i, l + 1, length, cnt);
            cnt[i]++;
        }
    }

}

性能

目标

给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：

• 选择一个下标 i ，它在之前的操作中 没有 被选择过。
• 将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。

示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 0 <= k <= 10^5
• 0 <= numOperations <= nums.length

思路

对数组 nums 执行 numOperations 次操作，每次操作可以选一个没有被操作过的元素，将其增加 [-k, k] 之间的整数，求元素值的最大出现次数。

对数组排序，并针对元素进行计数，枚举值域范围内的每一个值，二分查找左右 k 范围内的元素个数。

代码

/**
 * @date 2025-10-21 8:53
 */
public class MaxFrequency3346 {

    public int maxFrequency(int[] nums, int k, int numOperations) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] cnt = new int[max + 1];
        for (int num : nums) {
            cnt[num]++;
        }
        Arrays.sort(nums);
        int res = 1;
        for (int i = 1; i <= max; i++) {
            int l = lowerBound(nums, i - k);
            int r = upperBound(nums, i + k);
            res = Math.max(res, cnt[i] + Math.min(r - l + 1 - cnt[i], numOperations));
        }
        return res;
    }

    public int lowerBound(int[] nums, int target) {
        int r = nums.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (nums[mid] >= target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            mid = l + (r - l) / 2;
        }
        return l;
    }

    public int upperBound(int[] nums, int target) {
        int r = nums.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
            mid = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k。

你可以对数组中的每个元素 最多 执行 一次 以下操作：

• 将一个在范围 [-k, k] 内的整数加到该元素上。

返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。

示例 1：

输入： nums = [1,2,2,3,3,4], k = 2
输出： 6
解释：
对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。

示例 2：

输入： nums = [4,4,4,4], k = 1
输出： 3
解释：
对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

有一个整数数组 nums，允许对数组中的每个元素加上 [-k, k] 的整数，求操作后数组中不同元素的最大个数。

先对数组进行排序，计算相同元素个数，同时记录前一个元素操作后的最大值 + 1，当前相同元素的个数可以操作变成不同元素的范围是 [Math.max(nums[start] - k, prev), Math.min(nums[start] + k, l + cnt - 1)]。

代码

/**
 * @date 2025-10-20 10:09
 */
public class MaxDistinctElements3397 {

    public int maxDistinctElements(int[] nums, int k) {
        int n = nums.length;
        int i = 0;
        int prev = Integer.MIN_VALUE;
        int res = 0;
        Arrays.sort(nums);
        while (i < n) {
            int start = i;
            while (i < n && nums[i] == nums[start]) {
                i++;
            }
            int cnt = i - start;
            int l = Math.max(nums[start] - k, prev);
            int r = Math.min(nums[start] + k, l + cnt - 1);
            res += r - l + 1;
            prev = r + 1;
        }
        return res;
    }

}

性能