How do I efficiently find weak characters in this game problem?

Sort characters by descending attack and ascending defense, then use a running maximum or stack to detect those with strictly lower defense than previously seen characters.

Why do we group characters with the same attack before comparison?

Grouping prevents characters from being incorrectly counted as weak against others with identical attack values, satisfying the strict inequality requirement.

Can I use nested loops to compare all characters?

Nested loops are correct but inefficient; they lead to O(n^2) time. Using sorting with stack-based state management reduces time to O(n log n).

Does this approach work if defense values are very large?

Yes, because the algorithm only tracks the maximum defense seen so far, independent of absolute value size.

What pattern does this problem primarily follow?

It follows a stack-based state management pattern, where sorting and maintaining running maxima allow efficient identification of weak characters.

#1996

Medium

auto_awesome栈·状态

LeetCode 题解工作台

游戏中弱角色的数量

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击和防御。给你一个二维整数数组 properties ，其中 properties[i] = [attack i , defense i ] 表示游戏中第 i 个角色的属性。如果存在一个其他角色的攻击和防御等级都严格高于该角色的攻击…

数组栈贪心排序单调栈

题目描述

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

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

返回 弱角色 的数量。

示例 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 <= 10⁵
properties[i].length == 2
1 <= attack_i, defense_i <= 10⁵

lightbulb

解题思路

方法一：排序 + 遍历

我们可以将所有角色按照攻击力降序排序，防御力升序排序。

然后遍历所有角色，对于当前角色，如果其防御力小于之前的最大防御力，则说明其为弱角色，答案加一，否则更新最大防御力。

遍历结束后，即可得到答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为角色数量。

1

2

3

4

5

6

7

8

9

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x: (-x[0], x[1]))
        ans = mx = 0
        for _, x in properties:
            ans += x < mx
            mx = max(mx, x)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about sorting strategy and handling ties in attack values.
question_mark
Probe if the candidate can maintain state efficiently without nested loops.
question_mark
Check understanding of strict inequality and grouping by attack.

warning

常见陷阱

外企场景

error
Failing to group characters with the same attack before comparison.
error
Counting characters as weak against others with the same attack.
error
Using nested loops leading to O(n^2) time instead of optimized O(n log n).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return indices of all weak characters instead of just the count.
arrow_right_alt
Modify the problem to allow weak characters if only one attribute is strictly less.
arrow_right_alt
Apply the same stack-based approach to 3D attributes including speed or magic.

help

常见问题

外企场景

继续练习

#2818 操作使得分最大 #769 最多能完成排序的块 #768 最多能完成排序的块 II