第433场周赛：变长子数组求和、最多 K 个元素的子序列的最值之和、粉刷房子 Ⅳ、最多 K 个元素的子数组的最值之和

Q1、变长子数组求和

1、题目描述

给你一个长度为 n 的整数数组 nums 。对于每个下标 i（0 <= i < n），定义对应的子数组 nums[start ... i]（start = max(0, i - nums[i])）。

返回为数组中每个下标定义的子数组中所有元素的总和。

子数组 是数组中的一个连续、非空的元素序列。

2、解题思路

由于子数组的起点 start 取决于 nums[i]，每次计算 nums[start ... i] 的和时，我们可以借助 前缀和 来快速计算子数组的和，从而避免重复计算。

前缀和的定义

前缀和数组 prefix_sum[i] 表示 从数组开始到索引 i-1 的元素之和，即：

$prefix_sum [ i ] = ∑ j = 0 i − 1 nums [ j ] \text{prefix\_sum}[i] = \sum_{j=0}^{i-1} \text{nums}[j]$

则某个区间 [start, i] 的子数组和可以通过前缀和快速计算：

$prefix_sum [ i + 1 ] − prefix_sum [ start ] \sum_{j=\text{start}}^{i} \text{nums}[j] = \text{prefix\_sum}[i+1] - \text{prefix\_sum}[\text{start}]$

这样，我们可以在 O(1) 时间内计算每个 i 对应的子数组的和，而不会重复累加相同的元素，整体时间复杂度 降为 O(n)。

3、代码实现

class Solution {
public:int subarraySum(vector<int>& nums) {int n = nums.size();vector<int> prefix_sum(n + 1, 0); // 前缀和数组, prefix_sum[i] 表示 nums[0] 到 nums[i-1] 的和// 计算前缀和for (int i = 0; i < n; ++i) {prefix_sum[i + 1] = prefix_sum[i] + nums[i];}int result = 0; // 存储所有子数组的元素和for (int i = 0; i < n; ++i) {int start = max(0, i - nums[i]); // 计算子数组的起始位置result += prefix_sum[i + 1] - prefix_sum[start]; // 使用前缀和计算子数组和}return result;}
};

在这里插入图片描述

4、复杂度分析

前缀和计算 需要 O(n) 的时间。

子数组求和 通过前缀和的方式优化，每次 O(1)，整体仍然是 O(n)。

空间复杂度：使用额外的前缀和数组 O(n)，因此 空间复杂度 O(n)。

Q2、最多 K 个元素的子序列的最值之和

1、题目描述

给你一个整数数组 nums 和一个正整数 k，返回所有长度最多为 k 的 子序列 中 最大值 与 最小值 之和的总和。

非空子序列 是指从另一个数组中删除一些或不删除任何元素（且不改变剩余元素的顺序）得到的数组。

由于答案可能非常大，请返回对 109 + 7 取余数的结果。

2、解题思路

思路：数学 + 组合数优化计算

(1) 排序数组，便于计算最小值和最大值

假设 nums 排序后为：nums = [a1, a2, ..., an]

nums[i] 作为子序列的 最小值 时，其前面的 i 个元素可以自由选择（或不选），最大长度不超过 k。
nums[i] 作为子序列的 最大值 时，其后面的 n - i - 1 个元素可以自由选择，最大长度不超过 k。

(2) 计算 nums[i] 作为最小值的贡献

nums[i] 作为 最小值 时，所有子序列来自 [i, n-1] 的元素。
对于长度 ≤ k 的子序列，其前 i 个元素可以选，也可以不选，形成的子序列数为：

$\sum_{j=0}^{\min(k, i)} C(i, j)$

其中 C(i, j) 是组合数，即：

$\frac{i!}{j! (i-j)!}$

(3) 计算 nums[i] 作为最大值的贡献

由于 nums[i] 作为最大值时，其对称位置 nums[n - 1 - i] 作为最小值，因此我们直接计算 nums[i] 和 nums[n - 1 - i] 的贡献之和。

(4) 预计算阶乘与逆元，加速组合数计算

由于 C(n, m) 的计算涉及 阶乘求逆，直接计算 C(n, m) 可能会超时，因此我们使用 预计算 + 逆元 快速求解：

预计算阶乘 factorial[i] = i! % MOD
预计算 阶乘逆元 invFactorial[i] = (i!)^{-1} % MOD
通过 快速幂求逆元 (Fermat 小定理)

3、代码实现

const int MOD = 1000000007;
const int MAX_N = 100000;long long factorial[MAX_N]; // 存储阶乘 F[i] = i!
long long invFactorial[MAX_N];long long powerMod(long long x, int n) {long long res = 1;while (n > 0) {if (n & 1) // 如果 n 是奇数{res = res * x % MOD;}x = x * x % MOD;n >>= 1; // n 右移, 相当于除以 2}return res;
}// 预处理阶乘及其逆元
void precomputeFactorial() {factorial[0] = 1;for (int i = 1; i < MAX_N; ++i) {factorial[i] = factorial[i - 1] * i % MOD;}// 计算 (MAX_N - 1)! 的逆元invFactorial[MAX_N - 1] = powerMod(factorial[MAX_N - 1], MOD - 2);// 计算所有 (i!)^-1for (int i = MAX_N - 2; i >= 0; --i) {invFactorial[i] = invFactorial[i + 1] * (i + 1) % MOD;}
}// 计算组合数 C(n, m) = n! / (m! * (n-m)!)
long long comb(int n, int m) {if (m > n || m < 0) {return 0;}return factorial[n] * invFactorial[m] % MOD * invFactorial[n - m] % MOD;
}// 预处理组合数
auto _ = (precomputeFactorial(), 0);class Solution {
public:int minMaxSums(vector<int>& nums, int k) {sort(nums.begin(), nums.end()); // 先排序, 方便计算 min/maxint n = nums.size();long long totalSum = 0;// 计算所有长度 <= k 的子序列贡献for (int i = 0; i < n; ++i) {long long subsetCount = 0;// 计算 nums[i] 作为最小值的贡献for (int j = 0; j < min(k, i + 1); ++j) {subsetCount = (subsetCount + comb(i, j)) % MOD;}// 计算 nums[i] 作为最大值的对称贡献totalSum = (totalSum + subsetCount * (nums[i] + nums[n - 1 - i]) % MOD) % MOD;}return totalSum;}
};

在这里插入图片描述

4、复杂度分析

排序：O(n log n)

预处理阶乘和逆元：O(n)

计算所有 C(i, j)：最坏情况下 O(nk)，但一般远小于 O(n^2)。

最终复杂度：O(n log n + n + nk) ≈ O(n log n + nk)

Q3、粉刷房子 Ⅳ

1、题目描述

给你一个偶数整数 n，表示沿直线排列的房屋数量，以及一个大小为 n x 3 的二维数组 cost，其中 cost[i][j] 表示将第 i 个房屋涂成颜色 j + 1 的成本。

如果房屋满足以下条件，则认为它们看起来漂亮：

不存在两个涂成相同颜色的相邻房屋。
距离行两端等距的房屋不能涂成相同的颜色。例如，如果 n = 6，则位置 (0, 5)、(1, 4) 和 (2, 3) 的房屋被认为是等距的。

返回使房屋看起来漂亮的最低涂色成本。

2、解题思路

题目转化

由于房屋成对对称，我们可以将问题转换为处理 n/2 对房屋：

(0, n-1), (1, n-2), …, (n/2 - 1, n/2)

定义 dp[i][prevLeft][prevRight]：

表示前 i+1 对房屋（0 到 i），上一对房屋 (i-1) 选择了 prevLeft 和 prevRight 颜色时，符合要求的最低涂色成本。

动态规划状态定义

dp[i][leftColor][rightColor]：表示涂完第 i 对房屋，并且当前这对房屋的左房屋涂 leftColor，右房屋涂 rightColor 的最小成本。
递推关系：
- 枚举上一个房屋对 (i-1) 的颜色 prevLeft 和 prevRight。
- 确保 leftColor ≠ prevLeft，rightColor ≠ prevRight，并且 leftColor ≠ rightColor。
- 计算新的 dp[i][leftColor][rightColor] 的最小值。

3、代码实现

class Solution {
public:long long minCost(int n, vector<vector<int>>& cost) {// 动态规划数组 dp[i][prevLeft][prevRight]vector<vector<vector<long long>>> dp(n / 2 + 1, vector<vector<long long>>(3, vector<long long>(3, LLONG_MAX)));// 初始化 dp[0], 即第 0 对房屋的所有可能涂色情况for (int leftColor = 0; leftColor < 3; leftColor++) {for (int rightColor = 0; rightColor < 3; rightColor++) {// 初始状态不能相同if (leftColor != rightColor) {dp[0][leftColor][rightColor] = cost[0][leftColor] + cost[n - 1][rightColor];}}}// 动态规划计算所有房屋对的最小涂色成本for (int i = 1; i < n / 2; i++) {for (int prevLeft = 0; prevLeft < 3; prevLeft++) {for (int prevRight = 0; prevRight < 3; prevRight++) {// 如果上一对房屋 (i-1) 没有有效涂色方案, 跳过if (dp[i - 1][prevLeft][prevRight] == LLONG_MAX) {continue;}for (int leftColor = 0; leftColor < 3; leftColor++) {// 左房颜色不能和上一对左房相同if (leftColor == prevLeft) {continue;}for (int rightColor = 0; rightColor < 3; rightColor++) {// 右房颜色不能和上一对右房或左房相同if (rightColor == prevRight || rightColor == leftColor) {continue;}// 计算当前房屋对的成本long long currCost = cost[i][leftColor] + cost[n - 1 - i][rightColor];// 更新最小成本dp[i][leftColor][rightColor] = min(dp[i][leftColor][rightColor], dp[i - 1][prevLeft][prevRight] + currCost);}}}}}// 计算最终答案: 取最后一对房屋的所有可能涂色方案中的最小值long long minCost = LLONG_MAX;for (int leftColor = 0; leftColor < 3; leftColor++) {for (int rightColor = 0; rightColor < 3; rightColor++) {minCost = min(minCost, dp[n / 2 - 1][leftColor][rightColor]);}}return minCost;}
};

在这里插入图片描述

4、复杂度分析

状态数量：O(n/2 * 3 * 3) ≈ O(n)
转移复杂度：每个 dp[i] 依赖于 dp[i-1]，共 O(3^4) = O(81) 种情况。

总体复杂度： $\times 81) = O(n)$ 对于 n ≤ 10^4 仍然可以接受。

Q4、最多 K 个元素的子数组的最值之和

1、题目描述

给你一个整数数组 nums 和一个正整数 k 。返回最多有 k 个元素的所有子数组的最大和最小元素之和。

子数组 是数组中的一个连续、非空的元素序列。

2、解题思路

我们采用 单调栈 和 数学公式 进行高效计算：

如何计算所有子数组的最小值贡献？
- 使用单调递增栈，维护子数组的最小值，并计算它们的贡献。
- 当栈顶元素比当前元素 大于等于 时，说明它无法继续作为最小值，弹出栈并计算贡献。
- 贡献计算的核心在于，一个元素在多少个子数组中作为最小值。
如何计算所有子数组的最大值贡献？
- 只需取反 nums 数组，将最大值问题转化为最小值问题，再计算一次即可。
如何计算子数组个数？
- 数学公式：
  设子数组的长度为 m，若 m ≤ k，则该长度的所有子数组个数为： m(m+1)2\frac{m(m+1)}{2}2m(m+1) 若 m > k，则受 k 限制，其计算公式如下： (m×2−k+1)×k2\frac{(m \times 2 - k + 1) \times k}{2}2(m×2−k+1)×k
- 这个公式的推导基于滑动窗口思想，保证所有长度最多为 k 的子数组都被正确计算。

3、代码实现

class Solution {
public:long long minMaxSubarraySum(vector<int>& nums, int k) {// 计算长度为 m 的所有子数组的个数 (最多 k 个元素)auto countSubarrays = [&](int m) -> long long {return (m > k) ? 1LL * (m * 2 - k + 1) * k / 2 : 1LL * (m + 1) * m / 2;};// 计算所有子数组的最小值贡献auto sumSubarrayMins = [&](vector<int>& arr) -> long long {long long totalSum = 0;stack<int> st;st.push(-1); // 哨兵，方便计算边界for (int r = 0; r < arr.size(); r++) {// 维护单调递增栈, 保证栈中元素递增while (st.size() > 1 && arr[st.top()] >= arr[r]) {int i = st.top(); // 取出栈顶元素st.pop();int l = st.top(); // 栈顶元素的左边界// 计算该元素 arr[i] 作为最小值的贡献long long count = countSubarrays(r - l - 1) - countSubarrays(i - l - 1) - countSubarrays(r - i - 1);totalSum += arr[i] * count;}st.push(r);}return totalSum;};// 在 nums 末尾添加一个特殊值, 使得所有元素都能出栈计算贡献nums.push_back(INT_MIN / 2);long long ret = sumSubarrayMins(nums);// 取反 nums, 将最大值问题转化为最小值问题for (int& num : nums) {num = -num;}nums.back() *= -1; // 修正末尾特殊值ret -= sumSubarrayMins(nums);return ret;}
};

在这里插入图片描述