golang力扣leetcode 1996.游戏中弱角色的数量

1996.游戏中弱角色的数量 1996.游戏中弱角色的数量题解代码

1996.游戏中弱角色的数量

1996.游戏中弱角色的数量

题解

第一种做法：按照攻击力从大到小排序，相同攻击力则按照防御力从小到大排序，遍历切片，如果当前元素的防御小于维护的最大的防御，说明这个元素是最弱的，因为当前元素的攻击因为排序必定小于上一个，而防御又小于维护的最大防御，此时ans++，如果当前元素的防御大于维护的防御，则更新维护的最大防御

第二种做法：按照攻击力从小到大排序，相同攻击力则按照防御力从大到小排序，遍历切片，然后看for循环的代码

代码

package main

import "sort"

func numberOfWeakCharacters1(properties [][]int) int {
	sort.Slice(properties, func(i, j int) bool {
		return properties[i][0] > properties[j][0] ||
			properties[i][0] == properties[j][0] && properties[i][1] < properties[j][1]
	})
	defense := 0
	ans := 0
	for _, v := range properties {
		if v[1] < defense {
			ans++
		} else {
			defense = v[1]
		}
	}
	return ans
}
func numberOfWeakCharacters2(properties [][]int) int {
	sort.Slice(properties, func(i, j int) bool {
		return properties[i][0] < properties[j][0] ||
			properties[i][0] == properties[j][0] && properties[i][1] > properties[j][1]
	})
	ans := 0
	var cnt []int
	for _, v := range properties {
		for len(cnt) > 0 && cnt[len(cnt)-1] < v[1] {
			ans++
			cnt = cnt[:len(cnt)-1]
		}
		cnt = append(cnt, v[1])
	}
	return ans
}