Hard
题目描述
给你一个整数数组 nums。
如果 nums 的一个子数组不包含逆序对，即不存在下标对 i < j 使得 nums[i] > nums[j]，则称该子数组是稳定的。
同时给你一个长度为 q 的二维整数数组 queries，其中 queries[i] = [li, ri] 表示一个查询。对于每个查询 [li, ri]，计算完全位于区间 nums[li..ri] 内的稳定子数组的数量。
返回一个长度为 q 的整数数组 ans，其中 ans[i] 是第 i 个查询的答案。
注意：
- 单个元素的子数组被认为是稳定的。
示例 1：
输入：nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]
输出：[2,3,4]
解释：
- 对于 queries[0] = [0, 1]，子数组是 [3, 1]。
稳定的子数组有 [3] 和 [1]，总数为 2。
- 对于 queries[1] = [1, 2]，子数组是 [1, 2]。
稳定的子数组有 [1]、[2] 和 [1, 2]，总数为 3。
- 对于 queries[2] = [0, 2]，子数组是 [3, 1, 2]。
稳定的子数组有 [3]、[1]、[2] 和 [1, 2]，总数为 4。
示例 2：
输入：nums = [2,2], queries = [[0,1],[0,0]]
输出：[3,1]
约束条件：
1 <= nums.length <= 10^51 <= nums[i] <= 10^51 <= queries.length <= 10^5queries[i] = [li, ri]0 <= li <= ri <= nums.length - 1
解题思路
解题思路
核心观察： 稳定子数组就是非递减子数组，即不存在逆序对的子数组。
关键洞察：
- 我们需要找到所有最大的非递减段，每个长度为
L的段贡献L * (L + 1) / 2个稳定子数组 - 对于查询
[l, r]，我们需要快速计算该区间内的稳定子数组数量
算法步骤：
预处理阶段：
- 找到每个位置能向左扩展的最大非递减段长度
- 构建前缀和数组，记录以每个位置结尾的稳定子数组总数
查询处理：
- 使用前缀和快速计算区间内的稳定子数组数量
- 需要特别处理跨越查询左边界的子数组
具体实现：
dp[i]表示以位置i结尾的稳定子数组数量prefix[i]表示前i+1个位置的稳定子数组总数- 对于查询
[l, r]，答案是prefix[r] - prefix[l-1]再减去跨越左边界的多余部分
时间复杂度为 O(n + q)，空间复杂度为 O(n)，能够高效处理大规模数据。
代码实现
class Solution {
public:
vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<long long> dp(n), prefix(n);
// dp[i] = number of stable subarrays ending at i
dp[0] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] >= nums[i-1]) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = 1;
}
}
// prefix[i] = total stable subarrays in [0, i]
prefix[0] = dp[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + dp[i];
}
vector<long long> result;
for (auto& query : queries) {
int l = query[0], r = query[1];
long long total = prefix[r] - (l > 0 ? prefix[l-1] : 0);
// Subtract overcounted subarrays that start before l but end at or after l
if (l > 0 && nums[l] >= nums[l-1]) {
long long len = 1;
int j = l - 1;
while (j > 0 && nums[j] >= nums[j-1]) {
len++;
j--;
}
total -= len * (len + 1) / 2 - dp[l-1];
}
result.push_back(total);
}
return result;
}
};
class Solution:
def countStableSubarrays(self, nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
dp = [0] * n
prefix = [0] * n
# dp[i] = number of stable subarrays ending at i
dp[0] = 1
for i in range(1, n):
if nums[i] >= nums[i-1]:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
# prefix[i] = total stable subarrays in [0, i]
prefix[0] = dp[0]
for i in range(1, n):
prefix[i] = prefix[i-1] + dp[i]
result = []
for l, r in queries:
total = prefix[r] - (prefix[l-1] if l > 0 else 0)
# Subtract overcounted subarrays that start before l but end at or after l
if l > 0 and nums[l] >= nums[l-1]:
length = 1
j = l - 1
while j > 0 and nums[j] >= nums[j-1]:
length += 1
j -= 1
total -= length * (length + 1) // 2 - dp[l-1]
result.append(total)
return result
public class Solution {
public long[] CountStableSubarrays(int[] nums, int[][] queries) {
int n = nums.Length;
long[] dp = new long[n];
long[] prefix = new long[n];
// dp[i] = number of stable subarrays ending at i
dp[0] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] >= nums[i-1]) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = 1;
}
}
// prefix[i] = total stable subarrays in [0, i]
prefix[0] = dp[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + dp[i];
}
long[] result = new long[queries.Length];
for (int q = 0; q < queries.Length; q++) {
int l = queries[q][0], r = queries[q][1];
long total = prefix[r] - (l > 0 ? prefix[l-1] : 0);
// Subtract overcounted subarrays that start before l but end at or after l
if (l > 0 && nums[l] >= nums[l-1]) {
long length = 1;
int j = l - 1;
while (j > 0 && nums[j] >= nums[j-1]) {
length++;
j--;
}
total -= length * (length + 1) / 2 - dp[l-1];
}
result[q] = total;
}
return result;
}
}
var countStableSubarrays = function(nums, queries) {
const n = nums.length;
const dp = new Array(n);
const prefix = new Array(n);
// dp[i] = number of stable subarrays ending at i
dp[0] = 1;
for (let i = 1; i < n; i++) {
if (nums[i] >= nums[i-1]) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = 1;
}
}
// prefix[i] = total stable subarrays in [0, i]
prefix[0] = dp[0];
for (let i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + dp[i];
}
const result = [];
for (const [l, r] of queries) {
let total = prefix[r] - (l > 0 ? prefix[l-1] : 0);
// Subtract overcounted subarrays that start before l but end at or after l
if (l > 0 && nums[l] >= nums[l-1]) {
let length = 1;
let j = l - 1;
while (j > 0 && nums[j] >= nums[j-1]) {
length++;
j--;
}
total -= Math.floor(length * (length + 1) / 2) - dp[l-1];
}
result.push(total);
}
return result;
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n + q) |
| 空间复杂度 | O(n) |
其中 n 是数组长度，q 是查询数量。预处理需要 O(n) 时间，每个查询需要 O(1) 时间处理。