Hard
题目描述
给你一个长度为 n 的整数数组 nums 和一个整数 k。
对于 nums 的每个子数组，你可以对其应用最多 k 次操作。每次操作中，你可以将子数组中的任意一个元素增加 1。
注意每个子数组都是独立考虑的，意味着对一个子数组所做的更改不会影响到另一个子数组。
返回经过最多 k 次操作后，能够变成非递减数组的子数组数量。
如果一个数组的每个元素都大于等于它前面的元素（如果存在的话），则称该数组为非递减数组。
示例 1：
输入：nums = [6,3,1,2,4,4], k = 7
输出：17
解释：在 nums 的所有 21 个可能的子数组中，只有子数组 [6, 3, 1], [6, 3, 1, 2], [6, 3, 1, 2, 4] 和 [6, 3, 1, 2, 4, 4] 无法在应用最多 k = 7 次操作后变成非递减数组。因此，非递减子数组的数量是 21 - 4 = 17。
示例 2：
输入：nums = [6,3,1,3,6], k = 4
输出：12
解释：子数组 [3, 1, 3, 6] 以及 nums 中所有元素个数不超过三个的子数组（除了 [6, 3, 1]）都可以在 k 次操作后变成非递减数组。有 5 个单元素子数组，4 个双元素子数组，2 个三元素子数组（除了 [6, 3, 1]），所以总共有 1 + 5 + 4 + 2 = 12 个子数组可以变成非递减数组。
约束条件：
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9
解题思路
这道题要求统计经过最多 k 次操作后能变成非递减的子数组数量。关键在于高效计算每个子数组需要的最少操作次数。
思路分析：
暴力方法：对每个子数组计算所需操作次数，时间复杂度 O(n³)，会超时。
稀疏表优化：按照提示使用稀疏表预计算。对于长度为 2^e 的子数组，我们可以用动态规划的思想将其分解为两个长度为 2^(e-1) 的子数组来计算。
关键观察：要使子数组 [l, r] 非递减，我们需要确保每个位置的值不小于前一个位置。贪心策略是尽量少地增加元素值。
稀疏表实现：
sp[e][i] = {lastElement, operations}表示子数组nums[i...i+2^e-1]变非递减所需的操作数和最后一个元素的值- 状态转移：合并两个相邻的子数组时，右半部分可能需要额外操作来保证与左半部分的连接处非递减
最终统计：对每个起点，使用二分查找找到最长的可行子数组，累加贡献。
这种方法的时间复杂度为 O(n log n)，空间复杂度为 O(n log n)。
代码实现
class Solution {
public:
long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int maxLog = 20; // log2(10^5) < 20
// sp[e][i] = {lastElement, operations}
vector<vector<pair<long long, long long>>> sp(maxLog, vector<pair<long long, long long>>(n));
// Base case: single elements
for (int i = 0; i < n; i++) {
sp[0][i] = {nums[i], 0};
}
// Fill sparse table
for (int e = 1; e < maxLog; e++) {
for (int i = 0; i <= n - (1 << e); i++) {
auto left = sp[e-1][i];
auto right = sp[e-1][i + (1 << (e-1))];
long long lastElement = right.first;
long long operations = left.second + right.second;
// Ensure non-decreasing at the junction
if (right.first < left.first) {
operations += left.first - right.first;
lastElement = left.first;
}
sp[e][i] = {lastElement, operations};
}
}
long long result = 0;
// For each starting position
for (int i = 0; i < n; i++) {
int left = i, right = n - 1;
int maxLen = 0;
// Binary search for maximum valid length
while (left <= right) {
int len = (left + right) / 2;
int j = i + len;
if (j >= n) {
right = len - 1;
continue;
}
// Calculate operations needed for subarray [i, j]
long long ops = 0;
long long lastVal = 0;
int pos = i;
for (int e = maxLog - 1; e >= 0; e--) {
if (pos + (1 << e) - 1 <= j) {
auto curr = sp[e][pos];
if (pos == i) {
ops = curr.second;
lastVal = curr.first;
} else {
ops += curr.second;
if (curr.first < lastVal) {
ops += lastVal - curr.first;
} else {
lastVal = curr.first;
}
}
pos += (1 << e);
}
}
if (ops <= k) {
maxLen = len + 1;
left = len + 1;
} else {
right = len - 1;
}
}
result += maxLen;
}
return result;
}
};
class Solution:
def countNonDecreasingSubarrays(self, nums: List[int], k: int) -> int:
n = len(nums)
max_log = 20
# sp[e][i] = [lastElement, operations]
sp = [[[0, 0] for _ in range(n)] for _ in range(max_log)]
# Base case: single elements
for i in range(n):
sp[0][i] = [nums[i], 0]
# Fill sparse table
for e in range(1, max_log):
for i in range(n - (1 << e) + 1):
left = sp[e-1][i]
right = sp[e-1][i + (1 << (e-1))]
last_element = right[0]
operations = left[1] + right[1]
# Ensure non-decreasing at the junction
if right[0] < left[0]:
operations += left[0] - right[0]
last_element = left[0]
sp[e][i] = [last_element, operations]
result = 0
# For each starting position
for i in range(n):
left, right = i, n - 1
max_len = 0
# Binary search for maximum valid length
while left <= right:
length = (left + right) // 2
j = i + length
if j >= n:
right = length - 1
continue
# Calculate operations needed for subarray [i, j]
ops = 0
last_val = 0
pos = i
for e in range(max_log - 1, -1, -1):
if pos + (1 << e) - 1 <= j:
curr = sp[e][pos]
if pos == i:
ops = curr[1]
last_val = curr[0]
else:
ops += curr[1]
if curr[0] < last_val:
ops += last_val - curr[0]
else:
last_val = curr[0]
pos += (1 << e)
if ops <= k:
max_len = length + 1
left = length + 1
else:
right = length - 1
result += max_len
return result
public class Solution {
public long CountNonDecreasingSubarrays(int[] nums, int k) {
int n = nums.Length;
int maxLog = 20;
// sp[e][i] = {lastElement, operations}
long[,][] sp = new long[maxLog, n][];
// Base case: single elements
for (int i = 0; i < n; i++) {
sp[0, i] = new long[] { nums[i], 0 };
}
// Fill sparse table
for (int e = 1; e < maxLog; e++) {
for (int i = 0; i <= n - (1 << e); i++) {
var left = sp[e-1, i];
var right = sp[e-1, i + (1 << (e-1))];
long lastElement = right[0];
long operations = left[1] + right[1];
// Ensure non-decreasing at the junction
if (right[0] < left[0]) {
operations += left[0] - right[0];
lastElement = left[0];
}
sp[e, i] = new long[] { lastElement, operations };
}
}
long result = 0;
// For each starting position
for (int i = 0; i < n; i++) {
int left = i, right = n - 1;
int maxLen = 0;
// Binary search for maximum valid length
while (left <= right) {
int length = (left + right) / 2;
int j = i + length;
if (j >= n) {
right = length - 1;
continue;
}
// Calculate operations needed for subarray [i, j]
long ops = 0;
long lastVal = 0;
int pos = i;
for (int e = maxLog - 1; e >= 0; e--) {
if (pos + (1 << e) - 1 <= j) {
var curr = sp[e, pos];
if (pos == i) {
ops = curr[1];
lastVal = curr[0];
} else {
ops += curr[1];
if (curr[0] < lastVal) {
ops += lastVal - curr[0];
} else {
lastVal = curr[0];
}
}
pos += (1 << e);
}
}
if (ops <= k) {
maxLen = length + 1;
left = length + 1;
} else {
right = length - 1;
}
}
result += maxLen;
}
return result;
}
}
var countNonDecreasingSubarrays = function(nums, k) {
const n = nums.length;
let count = 0;
for (let i = 0; i < n; i++) {
let operations = 0;
let maxVal = nums[i];
for (let j = i; j < n; j++) {
if (j === i) {
maxVal = nums[i];
} else {
if (nums[j] < maxVal) {
operations += maxVal - nums[j];
} else {
maxVal = nums[j];
}
}
if (operations <= k) {
count++;
} else {
break;
}
}
}
return count;
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n log n) |
| 空间复杂度 | O(n log n) |
相关题目
- . Non-decreasing Array (Medium)