前言

• 大家好，我是新人简书博主：「 个人主页」主要分享程序员生活、编程技术、* * 以及每日的LeetCode刷题记录，欢迎大家关注我，一起学习交流，谢谢！
• 正在坚持每日更新LeetCode每日一题，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
• 同时也在进行其他专项类型题目的刷题与题解活动，相关资料也会同步到「GitHub」上面 ~
• 今天是坚持写题解的32天(haha，从21年圣诞节开始的)，大家一起加油

• 每日一题：LeetCode：1996.游戏中弱角色的数量
  • 时间：2022-01-28
  • 力扣难度：Medium
  • 个人难度：Medium
  • 数据结构：数组
  • 算法：排序、单调栈

LeetCode每日一题.jpg

2022-01-28：LeetCode：1996.游戏中弱角色的数量

1. 题目描述

• 题目：原题链接

  • 你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。
  • 如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。
  • 更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。
  • 返回 弱角色 的数量。
  • 2 <= properties.length <= 10^5
  • properties[i].length == 2
  • 1 <= attacki, defensei <= 10^5

• 输入输出规范

  • 输入：二维数组，表示角色属性
  • 输出：弱角色个数

• 输入输出示例

  • 输入：properties = [[1,5],[10,4],[4,3]]
  • 输出：1

2. 方法一：排序

• 思路

  • 本题中，弱角色的定义是攻击、防御都小于另一个角色，因此可以先对二维数组按照攻击进行降序排列
  • 排序之后，对数组进行遍历，对于遍历到的当前元素，只要存在前面的元素的防御力比当前元素的大，就找到一个弱角色
  • 具体而言，为了判断前面的元素的防御力是否大于当前元素，我们可以维护一个变量，表示当前遍历过的元素中的最大防御值，只要当前元素防御值小于该最大值，就是弱元素
  • 此外，本题的数据中存在攻击力相等的元素，此时对于任意一个元素，如果最大防御值大于该元素的防御值，但是两者的攻击力相同，那么该元素就不是弱元素
  • 对于这一情况，我们可以定制数组排序的规则，当攻击力相同时，按照防御力升序排列
  • 这样做可以使得当遍历到同一个攻击力的多个元素时，先遍历到防御力小的元素并判断其是不是弱元素
  • 如果是弱元素，最大防御值不会改变，后续遍历到的同攻击力的元素所对比的最大防御值是高攻击力的元素

• 题解

  public int numberOfWeakCharacters(int[][] properties) {
      Arrays.sort(properties, (o1, o2) -> {
          return o1[0] == o2[0] ? (o1[1] - o2[1]) : (o2[0] - o1[0]);
      });
      int maxDefense = 0;
      int count = 0;
      for (int[] property : properties) {
          if (property[1] < maxDefense) {
              count++;
          } else {
              maxDefense = property[1];
          }
      }
      return count;
  }
  

• 复杂度分析：n 是二维数组的长度

  • 时间复杂度：
  • 空间复杂度：

3. 方法二：桶思想

• 思路

  • 使用排序API来完成本题的时间复杂度是线性对数级，那么是否可以优化到线性复杂度呢
  • 其实如果不存在相同攻击力、防御力的元素，那么可以通过一次遍历求得最大攻击力和最大防御力，然后再遍历一次数组判断当前元素是否小于两个最大值即可，是线性的复杂度
  • 那么，相当于只是多了存在相同攻击力、防御力的元素的情况，此时可以通过桶的思想维护一个辅助数组bucket ，用来存储每个大于该攻击力的元素中对应的最大防御力，可以成为局部最大防御力
  • 然后，同样是遍历数组，判断当前元素是否小于最大攻击力，且小于当前元素攻击力对应的 bucket 数组中保存的局部最大防御力

• 题解

  public int numberOfWeakCharacters(int[][] properties) {
      // 求最大攻击力
      int maxAttack = 0;
      for (int[] property : properties) {
          maxAttack = Math.max(maxAttack, property[0]);
      }
  
      // bucket数组，先存储每个攻击力对应的最大防御力
      int[] bucket = new int[maxAttack + 1];
      for (int[] property : properties) {
          bucket[property[0]] = Math.max(bucket[property[0]], property[1]);
      }
  
      // bucket数组，存储大于当前攻击力的元素的最大防御力
      int maxDefence = 0; // 已遍历过的元素中的最大防御力
      for (int i = maxAttack; i >= 0; i--) {
          int prev = maxDefence;
          maxDefence = Math.max(maxDefence, bucket[i]);
          bucket[i] = prev;
      }
  
      int count = 0;
      // 遍历寻找弱角色
      // 小于最大攻击力，小于比当前元素攻击力大的元素的最大防御力
      for (int[] property : properties) {
          if (property[0] < maxAttack && property[1] < bucket[property[0]]) {
              count++;
          }
      }
      return count;
  }
  

• 复杂度分析：n 是二维数组的长度

  • 时间复杂度：，C 是最大的攻击力
  • 空间复杂度：

最后

如果本文有所帮助的话，欢迎大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的其他平台，上面会更新Java面经、八股文、刷题记录等等，欢迎大家光临交流，谢谢！

• 「个人博客」
• 「掘金」
• 「LeetCode」