[数据结构与算法]排序+贪心 -leetcode-

1996. 游戏中弱角色的数量

题目描述

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。
如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。
返回 弱角色 的数量。

提示：

• $2<=properties.length<=10^5$
• $properties[i].length==2$
• $1<=attack[i],defense[i]<=10^5$

排序+贪心

有两个维度，即攻击 和 防御，必须要先固定一个维度，然后比较另外一个维度

思路：

1. 先排序：先按照攻击升序；若攻击相同，再按照防御降序排序
2. 从后向前遍历，并维护一个 max 记录当前 defence 的最大值（从后向前）:
   • 如果当前选手的防御力 严格小于 当前的最大defence值，即 properties[i][1] < max，则表明找到一个 “弱角色”，res++;
   • 否则，更新当前 properties[i][1] = max;

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (int[] o1, int[] o2) -> {
            // 先按照攻击升序
            if (o1[0] != o2[0]) return o1[0] - o2[0];
            // 再按照防御降序排序
            return o2[1] - o1[1];
        });
        System.out.println(Arrays.deepToString(properties));
        // 双指针
        int res = 0;
        int max = 0;
        int n = properties.length;
        for (int i = n - 1; i >= 0; i--) {
            if (properties[i][1] >= max) {
                max = properties[i][1];
            } else {
                res++;
            }
        }
        return res;
    }
}

• 时间复杂度：$O(nlogn)$ （快排）
• 空间复杂度：$O(logn)$ （快排堆内存占用）