原文链接: https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game

英文原文

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

 

Example 1:

Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Explanation: No character has strictly greater attack and defense than the other.

Example 2:

Input: properties = [[2,2],[3,3]]
Output: 1
Explanation: The first character is weak because the second character has a strictly greater attack and defense.

Example 3:

Input: properties = [[1,5],[10,4],[4,3]]
Output: 1
Explanation: The third character is weak because the second character has a strictly greater attack and defense.

 

Constraints:

• 2 <= properties.length <= 105
• properties[i].length == 2
• 1 <= attacki, defensei <= 105

中文题目

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

通过代码

高赞题解

将角色按照攻击从大到小排序，攻击相同的按照防御从小到大排序。

然后遍历数组，维护遍历过的角色的防御的最大值 $\textit{maxDef}$。对于当前角色 $p$，如果 $p$ 的防御小于 $\textit{maxDef}$，那么说明前面有防御比 $p$ 高的角色（记作 $q$）；同时，根据上面的排序规则，如果 $q$ 的攻击和 $p$ 相同，那么 $q$ 的防御不会超过 $p$，矛盾，因此 $q$ 的攻击必然大于 $p$，于是 $q$ 的攻防均高于 $p$，$p$ 是一个弱角色。

func numberOfWeakCharacters(a [][]int) (ans int) {
	sort.Slice(a, func(i, j int) bool { a, b := a[i], a[j]; return a[0] > b[0] || a[0] == b[0] && a[1] < b[1] })
	maxDef := 0
	for _, p := range a {
		if p[1] < maxDef {
			ans++
		} else {
			maxDef = p[1]
		}
	}
	return
}

统计信息

通过次数	提交次数	AC比率
5235	20634	25.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言