力扣1996. 游戏中弱角色的数量（#Day22）

from typing import List
from collections import defaultdict


def numberOfWeakCharacters(properties: List[List[int]]) -> int:
    res = 0
    prop_map = defaultdict(list)
    max_defence = 0
    # {攻击力：[防御力,]}
    for attack, defence in properties:
        prop_map[attack].append(defence)
    # 按攻击力对哈希表排序
    for attack in sorted(prop_map, reverse=True):
        for defence in prop_map[attack]:
            if defence < max_defence:
                res += 1
        # 维护最大防御力
        max_defence = max(max_defence, max(prop_map[attack]))
    return res


properties = [[1, 5], [10, 4], [4, 3], [1, 2]]
print(numberOfWeakCharacters(properties))  # 2

def double_pointer_solution(properties: List[List[int]]) -> int:
    properties.sort(key=lambda x: (-x[0], -x[1]))  # 按攻击力由大到小，按防御力由大到小
    res = 0
    max_defence = 0
    i = 0
    while i < len(properties):  # i指针遍历角色的攻击力
        j, cur_max, max_defence = i, max_defence, max(
            max_defence, properties[i][1])  # 取当前最大防御力和该角色防御力间的最大值
        # j指针在攻击力相等的情况维护当前攻击力下的防御力
        while j < len(properties) and properties[j][0] == properties[i][0]:
            if properties[j][1] < cur_max:
                res += 1  # 满足伤害溢出
            j += 1
        i = j
    return res


properties = [[1, 5], [10, 4], [4, 3], [1, 2]]
print(double_pointer_solution(properties))  # 2