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 <= 10^5
  • properties[i].length == 2
  • 1 <= attacki, defensei <= 10^5

解题思路

这道题的核心思路是排序优化。暴力解法需要 O(n²) 时间复杂度，但通过巧妙的排序策略可以优化到 O(n log n)。

主要思路：

  1. 排序策略：按攻击力降序排列，如果攻击力相同则按防御力升序排列
  2. 为什么这样排序：
    • 攻击力降序保证我们从高攻击力向低攻击力遍历
    • 相同攻击力时防御力升序，避免相同攻击力的角色互相判定为弱角色
  3. 单调栈优化：维护一个防御力的单调递减栈
    • 遍历排序后的数组，对于每个角色，栈中所有防御力小于等于当前角色的都可以被当前角色"击败"
    • 将这些角色标记为弱角色并从栈中移除

关键洞察：

  • 由于按攻击力降序排列，当前角色的攻击力一定不大于之前处理的角色
  • 如果当前角色的防御力也大于某个之前的角色，那么那个角色就是弱角色
  • 单调栈确保我们高效地找到所有这样的角色

这种方法避免了嵌套循环，将复杂度从 O(n²) 降到 O(n log n)。

代码实现

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        // 按攻击力降序，攻击力相同时按防御力升序
        sort(properties.begin(), properties.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        
        int count = 0;
        stack<int> st; // 存储防御力的单调递减栈
        
        for (const auto& prop : properties) {
            // 移除栈中防御力小于等于当前角色的所有角色（它们是弱角色）
            while (!st.empty() && st.top() < prop[1]) {
                st.pop();
                count++;
            }
            st.push(prop[1]);
        }
        
        return count;
    }
};

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        # 按攻击力降序，攻击力相同时按防御力升序
        properties.sort(key=lambda x: (-x[0], x[1]))
        
        count = 0
        stack = []  # 存储防御力的单调递减栈
        
        for attack, defense in properties:
            # 移除栈中防御力小于当前角色的所有角色（它们是弱角色）
            while stack and stack[-1] < defense:
                stack.pop()
                count += 1
            stack.append(defense)
        
        return count

public class Solution {
    public int NumberOfWeakCharacters(int[][] properties) {
        // 按攻击力降序，攻击力相同时按防御力升序
        Array.Sort(properties, (a, b) => a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        
        int count = 0;
        Stack<int> stack = new Stack<int>(); // 存储防御力的单调递减栈
        
        foreach (var prop in properties) {
            // 移除栈中防御力小于当前角色的所有角色（它们是弱角色）
            while (stack.Count > 0 && stack.Peek() < prop[1]) {
                stack.Pop();
                count++;
            }
            stack.Push(prop[1]);
        }
        
        return count;
    }
}

/**
 * @param {number[][]} properties
 * @return {number}
 */
var numberOfWeakCharacters = function(properties) {
    // 按攻击力降序，攻击力相同时按防御力升序
    properties.sort((a, b) => a[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，遍历和栈操作总共 O(n)
空间复杂度O(n)单调栈最多存储 n 个元素

相关题目