游戏中弱角色的数量

标签: 栈 贪心 数组 排序 单调栈

难度: Medium

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 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

Submission

运行时间: 386 ms

内存: 52.9 MB

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
      
        """
        :type properties: List[List[int]]
        :rtype: int
        """
        # 按照攻击力降序排序，攻击力相同则按照防御力升序排序
        properties.sort(key=lambda x: (-x[0], x[1]))
        max_defense = 0
        weak_count = 0
        # 遍历排序后的角色属性
        for _, defense in properties:
            # 如果当前角色的防御力小于之前遍历过的角色的最大防御力，则为弱角色
            if defense < max_defense:
                weak_count += 1
            else:
                max_defense = defense
        return weak_count

Explain

题解的核心思路是通过排序和一次遍历来确定弱角色的数量。首先，我们将角色按照攻击力进行降序排序，如果攻击力相同，则按照防御力升序排序。这样做的目的是：当我们在遍历列表时，每次遇到的角色，其后面的角色攻击力要么相同要么更小。因此，我们只需要关心防御力的比较。在遍历过程中，我们维护一个记录之前角色最大防御力的变量max_defense。对于每个角色，如果其防御力小于max_defense，则它是一个弱角色。这样，我们可以在单次遍历中完成弱角色的计数。

时间复杂度: O(n log n)

空间复杂度: O(log n)

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        # 按照攻击力降序排序，攻击力相同则按照防御力升序排序
        properties.sort(key=lambda x: (-x[0], x[1]))
        max_defense = 0  # 初始化记录最大防御力的变量
        weak_count = 0  # 初始化弱角色计数
        # 遍历排序后的角色属性
        for _, defense in properties:
            # 如果当前角色的防御力小于之前遍历过的角色的最大防御力，则为弱角色
            if defense < max_defense:
                weak_count += 1  # 计数增加
            else:
                max_defense = defense  # 更新最大防御力
        return weak_count  # 返回弱角色数量

Explore

按攻击力降序排序确保在遍历时，每个角色都不会遇到攻击力更高的角色，因此我们只需比较防御力。而防御力升序排序防止攻击力相同的角色中防御力较高的角色被错误地认定为弱角色。如果两者都按降序排序，防御力高的角色可能排在防御力低的角色之后，导致高防御力角色被错误地认为是弱角色。

不会。由于防御力是按升序排序的，当攻击力相同时，防御力较低的角色会先被处理，其防御力不会被认为是最大防御力。因此，随后遇到的防御力较高的角色不会被认为弱角色，因为其防御力会大于或等于之前角色的防御力。

因为我们只需要知道历史上遇到的最强的防御力来确定当前角色是否为弱角色。如果当前角色的防御力不高于max_defense，则该角色为弱角色，但这并不影响max_defense的值。只有当遇到更高的防御力时，才需要更新max_defense，以确保正确地评估后续角色。

是的，算法仍然有效。如果数组为空，排序不会改变数组，遍历开始时就会结束，返回的弱角色数为0。如果数组只包含一个角色，由于没有其他角色可以比较，该角色也不会被认为是弱角色，结果同样是0。