1、题干​

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

提示：

• 1 <= classes.length <= 105
• classes[i].length == 2
• 1 <= passi <= totali <= 105
• 1 <= extraStudents <= 105

2、思路​

这题思路比较容易想到，先用优先队列存储各个班级通过率 classes，优先队列排序逻辑是：假设这个班引入1个逢考必过的学霸 extraStudents 后通过率增长越多排序越靠前。

接着每次安排1个学霸进入通过率增长最多的班级，计算该班级通过率增长值并累加到最初的总通过率 rate，最后求平均就能得到最大平均通过率。

3、代码​

function maxAverageRatio(classes: number[][], c: number): number {
    const pq = new PriorityQueue({
        compare: (a: number[], b: number[]): number => {
            const da = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
            const db = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
            return db - da;
        }
    });

    let rate = 0;
    for (let i = 0; i < classes.length; i++) {
        pq.enqueue(classes[i]);
        rate += classes[i][0] / classes[i][1];
    }

    for (; c; c--) {
        const t = pq.dequeue();
        pq.enqueue([t[0] + 1, t[1] + 1]);
        rate += (t[0] + 1) / (t[1] + 1) - t[0] / t[1];
    }

    return rate / classes.length;
};

4、复杂度​

• 时间复杂度：$O(nlogn)$
• 时间复杂度：$O(n)$

5、执行结果​

1、题干​

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。

给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。

示例 1：

输入：amount = [1,4,2]
输出：4
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯温水。
第 2 秒：装满一杯温水和一杯热水。
第 3 秒：装满一杯温水和一杯热水。
第 4 秒：装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。

示例 2：

输入：amount = [5,4,4]
输出：7
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯热水。
第 2 秒：装满一杯冷水和一杯温水。
第 3 秒：装满一杯冷水和一杯温水。
第 4 秒：装满一杯温水和一杯热水。
第 5 秒：装满一杯冷水和一杯热水。
第 6 秒：装满一杯冷水和一杯温水。
第 7 秒：装满一杯热水。

示例 3：

输入：amount = [5,0,0]
输出：5
解释：每秒装满一杯冷水。

提示：

• amount.length == 3
• 0 <= amount[i] <= 100

2、思路​

假设杯子数量从少到多分别为 min、mid、max，首先得装满最多的杯子，因此存在两种情况：

• min + mid <= max，这种情况只需要 max 秒钟就能装满所有杯子
• min + mid > max，先装满最多的杯子，需要 max 秒钟
  • 另外两种杯子会剩余 min + mid - max 个，剩余杯子可能为奇数也可能为偶数，但两种杯子差值最多为 1，所以还需要 Math.ceil((mid + min - max) / 2) 秒钟

3、代码​

function fillCups(amount: number[]): number {
    const [min, mid, max] = amount.sort((a, b) => a - b);
    if (min + mid <= max) return max;
    return max + Math.ceil((mid + min - max) / 2);
};

4、复杂度​

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以 构造 出 x 。

请返回从 0 开始（包括 0 ），你最多能 构造 出多少个连续整数。

你可能有多个相同值的硬币。

示例 1：

输入：coins = [1,3]
输出：2
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
从 0 开始，你可以构造出 2 个连续整数。

示例 2：

输入：coins = [1,1,1,4]
输出：8
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
- 2：取 [1,1]
- 3：取 [1,1,1]
- 4：取 [4]
- 5：取 [4,1]
- 6：取 [4,1,1]
- 7：取 [4,1,1,1]
从 0 开始，你可以构造出 8 个连续整数。

示例 3：

输入：nums = [1,4,10,3,1]
输出：20

提示：

• coins.length == n
• 1 <= n <= 4 * 104
• 1 <= coins[i] <= 4 * 104

2、思路​

按递增顺序逐个使用硬币 c 与当前的 x 构造出下一个 x 的范围 $[min(c,x) , x+c]$；若 c > x+1 则表示从该硬币开始无法构造连续整数；最后结果返回 x+1

注意：这个算法中硬币不能重复使用

3、代码​

function getMaximumConsecutive(coins: number[]): number {
    coins.sort((a, b) => a - b);

    let x = 0;
    for (const c of coins) {
        if (c <= x + 1) x = x + c;
    }

    return x + 1;
};

4、复杂度​

• 时间复杂度：$O(n*logn)$
• 空间复杂度：$O(logn)$

5、执行结果​

1、题干​

小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。

字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。

给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。

注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：

• x 是 y 的一个前缀；
• 如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。

示例 1：

输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。

示例 2：

输入：n = 5, k = 73
输出："aaszz"

提示：

• 1 <= n <= 105
• n <= k <= 26 * n

2、思路1​

数组+贪心模拟，使用长度为 n 的数组 codes 存储每个字符的 数值，数组 codes 之和代表 字符串的数值，初始化时 codes 所有元素都置为 1（代表字符 a），之后从数组尾部开始将元素替换成尽可能大的 数值 直至 k 为 0

3、代码​

function getSmallestString(n: number, k: number): string {
    k = k - n;
    const codes = new Array(n).fill(1);

    for (let i = codes.length - 1; i > -1 && k > 0; i--) {
        codes[i] = Math.min(k + 1, 26);
        k = k - codes[i] + 1;
    }

    return codes.map(c => String.fromCharCode(96 + c)).join('');
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

虽然时间复杂度和空间复杂度已经很不错，但是由于数组存储数据，以及字符串操作过多导致消耗的时间和内存偏高。下面对此稍加优化。

6、思路2​

从上述模拟过程可以推断出，所求最小字符串的形式是 aaaaamzzzzz，即 若干个 a + 一个中间字符 + 若干个 z。因此只要求出 a 的个数、z 的个数、以及中间字符，就能拼接出所求最小字符串。

7、代码​

function getSmallestString(n: number, k: number): string {
    let na = 0, nz = 0;
    for (k -= n; k >= 25; k -= 25)  nz++;
    na = n - nz - (k > 0 ? 1 : 0);

    const m = k > 0 ? String.fromCharCode(97 + k) : '';

    return 'a'.repeat(na) + m + 'z'.repeat(nz);
};

8、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

9、执行结果​

1、题干​

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：

• nums.length == n
• nums[i] 是 正整数 ，其中 0 <= i < n
• abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
• nums 中所有元素之和不超过 maxSum
• nums[index] 的值被 最大化

返回你所构造的数组中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

示例 1：

输入：n = 4, index = 2,  maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

示例 2：

输入：n = 6, index = 1,  maxSum = 10
输出：3

提示：

• 1 <= n <= maxSum <= 109
• 0 <= index < n

2、思路​

跟官解思路一贪心+二分查找相似，从均值 Math.ceil(maxSum / n) 开始枚举最大元素 nums[index]，然后按照贪心思路计算左右两边元素，其左右两边的元素是公差为 1 的递减的等差数列，递减到 1 之后其他元素都为 1，最后返回使得整个数组之和小于等于 maxSum 的最大 nums[index]。

3、代码​

function maxValue(n: number, index: number, maxSum: number): number {
    function sumNums(ak: number, k: number) {
        let sum = 0;
        const a0 = ak - (k - 1);
        
        if (k > 0) {
            if (a0 >= 1) sum += (a0 + ak) * k / 2;
            else {
                sum += (1 + ak) * ak / 2 + (k - ak);
            }
        }

        return sum;
    }

    function search(max: number) {
        let sum = -max;

        // sum:0 ~ index
        sum += sumNums(max, index + 1);

        // sum:index ~ n-1
        sum += sumNums(max, n - index);

        return sum <= maxSum;
    }

    const avg = Math.ceil(maxSum / n);
    for (let c = 0; c > -1; c++) {
        const valid = search(avg + c);
        if (!valid) return avg + c - 1;
    }
};

4、执行结果​

1、题干​

给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有一条重要属性：abs(nums[i]) <= limit 。

返回使数组元素总和等于 goal 所需要向数组中添加的 最少元素数量 ，添加元素 不应改变 数组中 abs(nums[i]) <= limit 这一属性。

注意，如果 x >= 0 ，那么 abs(x) 等于 x ；否则，等于 -x 。

示例 1：

输入：nums = [1,-1,1], limit = 3, goal = -4
输出：2
解释：可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。

示例 2：

输入：nums = [1,-10,9,1], limit = 100, goal = 0
输出：1

提示：

• 1 <= nums.length <= 105
• 1 <= limit <= 106
• -limit <= nums[i] <= limit
• -109 <= goal <= 109

Problem: 1785. 构成特定和需要添加的最少元素

2、思路​

贪心，nums 总和大于 goal 时都转成相反数

Code

function minElements(nums: number[], limit: number, goal: number): number {
    const d = goal - nums.reduce((a, c) => a + c, 0);
    return d < 0 ? minElements(nums.map(n => -n), limit, -goal) : Math.ceil(d / limit);
};

3、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

4、执行结果​

1、题干​

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

提示：

• 1 <= nums1.length, nums2.length <= 105
• 1 <= nums1[i], nums2[i] <= 6

Problem: 1775. 通过最少操作次数使数组的和相等

2、思路​

题目要求使数组的和相等的最少操作次数，可以使用贪心算法。假设 nums1 的和较小，升序地将 nums1 中的数尽量变大（最大为 6），降序地将 nums2 中的数尽量变小（最小为 1），直到两个数组的和相等。

操作时需要同时处理 nums1 中的数 n 和 nums2 中的数 7-n。

3、Code​

function minOperations(nums1: number[], nums2: number[]): number {
    const n1 = nums1.length, n2 = nums2.length;
    if (n1 < n2 && 6 * n1 < n2 || (n2 < n1 && 6 * n2 < n1)) return -1;

    let sum1 = nums1.reduce((a, c) => a + c, 0);
    let sum2 = nums2.reduce((a, c) => a + c, 0);

    if (sum1 === sum2) return 0;
    if (sum1 > sum2) [sum1, sum2, nums1, nums2] = [sum2, sum1, nums2, nums1];

    const diffList = new Array(6).fill(0);
    for (let i = 0; i < Math.max(n1, n2); i++) {
        if (nums1[i]) diffList[6 - nums1[i]] += 1;
        if (nums2[i]) diffList[nums2[i] - 1] += 1;
    }

    let ans = 0, diff = sum2 - sum1;

    for (let d = 5; d > 0 && diff > 0; d--) {
        const u = Math.min(diffList[d], Math.ceil(diff / d));
        diff -= d * u;
        ans += u;
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

• s 是一个尽可能长的快乐字符串。
• s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
• s 中只含有 'a'、'b' 、'c' 三种字母。

如果不存在这样的字符串 s ，请返回一个空字符串 ""。

示例 1：

输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。

示例 2：

输入：a = 2, b = 2, c = 1
输出："aabbc"

示例 3：

输入：a = 7, b = 1, c = 0
输出："aabaa"
解释：这是该测试用例的唯一正确答案。

提示：

• 0 <= a, b, c <= 100
• a + b + c > 0

题目对我来说挺有难度，想了蛮久，用了两种思路，都是基于3种字母的数量关系解题，这里记录其中一种

2、解题思路​

总体思路

• 按数量对 'a'、'b' 、'c' 三种字母进行降序排序
• 由于快乐字符串中不能出现3个连续相同字符，可以先取数量最多的字母，每两个组成一个字符串并存入数组中，记为 arr
• 遍历 arr 中的所有字符串，把剩余字母逐个拼接到每个字符串末尾，由于剩余任意一种字母数量都不会超过 $2*arr.length$，因此任意一种字母必定可以在两轮循环内消耗完，且 arr 中任意一个字符串都不会出现3个连续相同字符
• 最后拼接所有字符串，只可能在末尾出现3个以上连续相同字符，把末尾多余字符处理掉即可

举个例子 ：a = 1, b = 1, c = 7

• 1、取数量最多的字母 c，每两个组成一个字符串，得到：['cc','cc','cc','c']
• 2、把剩余字母 a 逐个拼接到每个字符串末尾，得到：['cca','cc','cc','c']，此时一轮循环尚未结束
• 3、一轮循环没结束，字母 a 已耗尽，继续该轮循环，把剩余字母 b 逐个拼接到每个字符串末尾，得到：['cca','ccb','cc','c']
• 4、拼接所有字符串再处理末尾多余字符，得到：'ccaccbcc'

再举个例子 ：a = 6, b = 6, c = 6

• 1、取数量最多的字母 a，每两个组成一个字符串，得到：['aa','aa','aa']
• 2、把剩余字母 b 逐个拼接到每个字符串末尾，得到：['aab','aab','aab']，此时已结束一轮循环
• 3、一轮循环没有消耗所有字母 b，再来一轮，得到：['aabb','aabb','aabb']，此时已结束两轮循环
• 4、同理把剩余字母 c 逐个拼接到每个字符串末尾，得到：['aabbcc','aabbcc','aabbcc']
• 5、拼接所有字符串再处理末尾多余字符，得到：'aabbccaabbccaabbcc

3、代码​

var longestDiverseString = function (a, b, c) {
    const m = [['a', a], ['b', b], ['c', c]].sort((a, b) => b[1] - a[1]);

    const len = Math.ceil(m[0][1] / 2);
    const arr = new Array(len).fill(m[0][0] + m[0][0]);
    if (m[0][1] % 2) arr[len - 1] = m[0][0];

    for (let i = 0; m[1][1] || m[2][1]; i++) {
        if (m[1][1]) arr[i % len] += m[1][0], m[1][1]--;
        else arr[i % len] += m[2][0], m[2][1]--;
    }

    return arr.join('').replace(new RegExp(m[0][0] + '{3,}$'), m[0][0] + m[0][0]);
};

4、执行结果​

1、题干​

给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。

斐波那契数字定义为：

• F₁ = 1
• F₂ = 1
• F_n = F_n-1 + F_n-2 ， 其中 n > 2 。

数据保证对于给定的 k ，一定能找到可行解。

示例 1：

输入：k = 7
输出：2 
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。

示例 2：

输入：k = 10
输出：2 
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。

示例 3：

输入：k = 19
输出：3 
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。

提示：

• 1 <= k <= 10^9

2、代码​

var findMinFibonacciNumbers = function (k) {
    const nums = [1, 2];
    while (nums[nums.length - 1] < 1e9) nums.push(nums[nums.length - 1] + nums[nums.length - 2]);

    let n, count = 0;
    while (k && (n = nums.pop())) {
        if (n > k) continue;
        count += k / n >> 0;
        k = k % n;
    }
    
    return count;
};

3、执行结果​

1、题干​

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。

如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。

返回 弱角色 的数量。

示例 1：

输入：properties = [[5,5],[6,3],[3,6]]
输出：0
解释：不存在攻击和防御都严格高于其他角色的角色。

示例 2：

输入：properties = [[2,2],[3,3]]
输出：1
解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。

示例 3：

输入：properties = [[1,5],[10,4],[4,3]]
输出：1
解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。

提示：

• 2 <= properties.length <= 105
• properties[i].length == 2
• 1 <= attacki, defensei <= 105

没想到官解那么巧妙的解法，提供一个普通思路。。。

2、解法1​

方便起见将角色属性数组长度 properties.length 记为 $n$。

总体思路

• 先升序排序：对属性数组 properties 按攻击力升序排序
• 再查找强角色：假设攻击力没有相同值，对于任意角色 i 如果能在区间 $[i+1, n-1]$ 内找到一个防御力更大的角色 j，就说明 i 是一个弱角色
• 预统计区间内最大防御力，加速查找：问题是在区间 $[i+1, n-1]$ 内找一个比较大的值需要遍历，时间复杂度不允许，因此可以先统计区间内的最大值，在查找的时候直接使用最大值进行比较即可

大体步骤

• 先对属性数组 properties 按攻击力升序排序
• 创建数组 maxDefs 用于记录区间最大防御力，对于任意元素 maxDefs[i] 表示区间 $[i, n-1]$ 内的最大防御力
  • 这里需要倒序遍历 properties，对于任意索引 i，maxDefs[i] 取当前防御力 properties[i][1] 与后续区间最大防御力 maxDefs[i + 1] 中的最大值
  • 最后 maxDefs 会形成一个单调递减的数列
• 最后顺序遍历 properties ，对于任意角色属性 properties[i]，如果能在区间 $[i+1, n-1]$ 找到一个攻击力防御力都更大的角色属性 properties[j]，即 properties[i][0] < properties[j][0] && properties[i][1] < maxDefs[j]，则说明这是一个弱角色
  • 注意这里需要跳过攻击力相同的角色

3、代码​

var numberOfWeakCharacters = function (properties) {
    properties.sort((a, b) => a[0] - b[0]);

    const n = properties.length, maxDefs = new Array(n).fill(0);
    for (let i = n - 1; i > -1; i--) {
        maxDefs[i] = Math.max(maxDefs[i + 1] || 0, properties[i][1]);
    }

    let count = 0;
    for (let i = 0; i < n - 1; i++) {
        let j = i + 1;
        // 跳过攻击力相同的角色
        while (j < n && properties[i][0] === properties[j][0]) j++;
        if (properties[i][1] < maxDefs[j]) count++;
    }

    return count;
};

4、复杂度​

• 时间复杂度：$O(nlogn)$ 到 $O(n^2)$ 之间
• 空间复杂度：$O(n)$

5、执行结果​

• 执行用时: 344 ms，超97%
• 内存消耗: 75.2 MB，超7%

6、解法1-优化​

问题：跳过攻击力相同的角色是后置的，在查找过程中通过遍历的方式逐一跳过，这里增加了时间复杂度 优化：可以参考官解的排序方式：依然按攻击力升序排序，但是当攻击力相同时按防御力降序排序。这里很巧妙地规避了需要跳过攻击力相同角色的问题，因为攻击力相同时按防御力降序排序，意味着后续区间如果出现更大的防御力必定不属于攻击力相同的角色

7、代码​

var numberOfWeakCharacters = function (properties) {
    properties.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);

    const n = properties.length, maxDefs = new Array(n).fill(0);
    for (let i = n - 1; i > -1; i--) {
        maxDefs[i] = Math.max(maxDefs[i + 1] || 0, properties[i][1]);
    }

    let count = 0;
    for (let i = 0; i < n - 1; i++) {
        if (properties[i][1] < maxDefs[i + 1]) count++;
    }

    return count;
};

8、复杂度​

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$

9、执行结果​

• 执行用时: 336 ms，超97%
• 内存消耗: 74.8 MB，超7%

如果把优化后的代码调整为按攻击力降序排序或者按倒序遍历查找弱角色，就跟官解一样了，记录区间最大值不再需要数组，只需要一个变量，空间复杂度可以降到 $O(1)$，时间复杂度相同。