2681. 英雄的力量

难度: 困难

来源: 每日一题 2023.08.01

---

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

i0 ，i1 ，... ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])² * min(nums[i0],nums[i1] ... nums[ik]) 。
请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。

示例 1：

输入：nums = [2,1,4]
输出：141
解释：
第 1 组：[2] 的力量为 22 * 2 = 8 。
第 2 组：[1] 的力量为 12 * 1 = 1 。
第 3 组：[4] 的力量为 42 * 4 = 64 。
第 4 组：[2,1] 的力量为 22 * 1 = 4 。
第 5 组：[2,4] 的力量为 42 * 2 = 32 。
第 6 组：[1,4] 的力量为 42 * 1 = 16 。
第​ ​​​​​​7 组：[2,1,4] 的力量为 42​​​​​​​ * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。

示例 2：

输入：nums = [1,1,1]
输出：7
解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

class Solution {
    public int sumOfPower(int[] nums) {

    }
}

分析与题解

---

• 排序 + 前缀和 + 动态规划

  一开始我是想到使用动态规划, 原因是这样的, 我在想如果一个题求这种累加性质的问题一般是要使用到动态规划的性质解决, 例如最大值, 最小值等等. 但是像这个 英雄的力量 对于我来说, 想到动态规划的解决方案很简单, 但是如何创建状态转移方程以及状态转移方程所代表的具体意义是什么, 在没看到官方题解之前我是一脸懵逼的. 8月1号看了官方的题解之后, 我才了解了新的知识点, 那就是前缀和, 接下来我们一起看一下具体的解题过程.

  首先抛开所有的条件, 我们的着手点应该是

  max(nums[i0],nums[i1] ... nums[ik])² * min(nums[i0],nums[i1] ... nums[ik])

  上面的关系式表示我们取出任意一个子数组, 我们需要当前子数组中的最大值 MaxValue 和 最小值 MinValue. 也就说计算公式会变成如下所示.

  MaxValue² * MinValue

  这时候, 如果按照数组原来的顺序, 我们会怎么做呢? 我们会排序一下子数组, 然后取出首尾两个数值即为我们所需要的 最大值 MaxValue 和 最小值 MinValue.

  但是我们假设 i 为终点, 起始点只能比 i 小的情况下, 会有多少个子数组呢? 并且每一个子数组都需要重新排序,这时候时间复杂度会成倍的增长.

  那么我们何不一开始就把整个数组都排序完成呢? 因为数组的顺序是怎么样的, 最后的形成的子数组的个数是相同的, 也就说说 数组的排序对 形成子数组的个数以及包含元素是没有影响的, 不知道这么说对不对.....

  Arrays.sort(nums);
  

  我们把整个数组都进行了排序,然后查找某个子数组的 最大值 MaxValue 和 最小值 MinValue 时, 我们只需要取 首尾两个元素 即可. 并不需要再次对子数组进行排序.

  接下来, 我们就需要把逻辑思维再扩大一下, 当结束点为 下标i 时, 我们该如何求出所有的以 下标i 为结束点的 计算公式呢?

  也就是说 那么当 index = i 时, 排序完成的数组一共有多少种组合形式呢?

  

  如上图所示, 如果 i = 2 , 那么组合形式会有4种.

  [nums[0], nums[1], nums[2]]

  [nums[0], nums[2]]

  [nums[1], nums[2]]

  [nums[2]]

  ---

  我们可以如下进行推导.

  i = 0 → [nums[1]]

  i = 1 → [nums[0], nums[1]] [nums[1]]

  i = 2 → [nums[0], nums[1], nums[2]] [nums[0], nums[2]] [nums[1], nums[2]] [nums[2]]

  可以看到 当 index = i 时, 总共的排列组合个数实际上为

  index = 0 的组合个数 + index = 1 的组合个数 + ..... + index = i - 1 的组合个数 + 1个(自身即为起点也为终点)

  如果我们要计算 index = i 的 数值和, 那么就是如下计算. 可以根据上面的图片演示进行推导.

  index = 0 的所有组合数值和 + index = 1 的所有组合数值和 + . . . + index = i - 1 的所有组合数值和 + nums[i]

  如果每一个元素都要如此进行一遍的计算, 那么时间复杂度就变成了 O(n²), 整个题解肯定会超时的, 那么怎么办?

  这里我们就要使用到一个新的概念, 那就是 前缀和

  上面我们已经有了组合的推导公式, 我们也可以推导出 状态转移方式, 假设 pre[i] 代表着 在 下标i 之前所以组合的数值和, dp[i] 代表着 下标i 时所有的数据和.

  那么必然会有如下的公式

  dp[i] = nums[i] + pre[i - 1];
  
  pre[i + 1] = dp[i] + pre[i];
  

  起始值的话, 就如下所示.

  pre[0] = 0;
  
  dp[0] = nums[0];
  

  当然在计算的过程中需要进行对模取余操作.

  dp[i] = (nums[i] + pre[i]) % mod;
  

  pre[i+1] = (pre[i] + dp[i]) % mod;
  

  result = (int) ((result + (long) nums[i] * nums[i] % mod * dp[i]) % mod);
  if (result < 0) {
      result += mod;
  }
  

  所以, 总结一下, 这个题目实际上是拆解了两个状态转移方程.... 题目确实是有一些难度的....

  最后整体逻辑代码如下所示.

  class Solution {
      public int sumOfPower(int[] nums) {
          Arrays.sort(nums);
          int length = nums.length, result = 0, mod = 1000000007;
          int[] dp = new int[length];
          int[] pre = new int[length + 1];
          for (int i = 0; i < length; i++) {
              dp[i] = (nums[i] + pre[i]) % mod;
              pre[i+1] = (pre[i] + dp[i]) % mod;
              result = (int) ((result + (long) nums[i] * nums[i] % mod * dp[i]) % mod);
              if (result < 0) {
                  result += mod;
              }
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 一次遍历循环, 时间复杂度与数组长度相关.
  • 空间复杂度: O(2n), 两个状态转移方程的长度与 height 的长度成线性关系.

  结果如下所示.