Kimi LeetCode 3748. 统计稳定子数组的数目 Java实现

以下是 LeetCode 3748「统计稳定子数组的数目」的 Java 实现。

核心思路

稳定子数组的定义是「没有逆序对」，等价于子数组中的元素是非降序排列的。

因此，可以将原数组划分为若干个最长的非降序段。对于长度为 `k` 的段，其内部所有子数组都是稳定的，数量为 `k * (k + 1) / 2`。

对于每个查询 `[l, r]`，分三种情况处理：
1. `[l, r]` 完全落在同一段内：直接公式计算。
2. `[l, r]` 跨越多个段：分别计算左端不完整段、中间完整段（用前缀和）、右端不完整段的贡献，三者相加。

时间复杂度 `O((n + q) log n)`，空间复杂度 `O(n)`。

---

Java 代码

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
public long[] countStableSubarrays(int[] nums, int[][] queries) {
// seg: 每段非降序子数组的起始位置
List<Integer> seg = new ArrayList<>();
// s: 前缀和，s[i] 表示前 i 个完整段中稳定子数组的总数
List<Long> s = new ArrayList<>();
s.add(0L);

int l = 0;
int n = nums.length;
for (int r = 0; r < n; r++) {
// 当遇到下降时（nums[r] > nums[r+1]），或者到达末尾，结束当前段
if (r == n - 1 || nums[r] > nums[r + 1]) {
seg.add(l);
int k = r - l + 1;
s.add(s.get(s.size() - 1) + (long) k * (k + 1) / 2);
l = r + 1;
}
}

long[] ans = new long[queries.length];
for (int q = 0; q < queries.length; q++) {
int left = queries[q][0];
int right = queries[q][1];

// upperBound: 第一个大于 target 的 seg 下标
int i = upperBound(seg, left);
int j = upperBound(seg, right) - 1;

if (i > j) {
// [left, right] 完全落在同一段内
int k = right - left + 1;
ans[q] = (long) k * (k + 1) / 2;
} else {
// 左不完整段长度
int a = seg.get(i) - left;
// 右不完整段长度
int b = right - seg.get(j) + 1;
ans[q] = (long) a * (a + 1) / 2 // 左端贡献
+ s.get(j) - s.get(i) // 中间完整段贡献
+ (long) b * (b + 1) / 2; // 右端贡献
}
}
return ans;
}

// 二分查找：返回第一个大于 target 的元素下标
private int upperBound(List<Integer> list, int target) {
int l = 0, r = list.size();
while (l < r) {
int mid = (l + r) >> 1;
if (list.get(mid) > target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
```

---

示例验证

以 `nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]` 为例：

- 非降序段划分：`[3]`（段0，起始0）、`[1,2]`（段1，起始1）
- 段0 长度1 → 贡献 `1`；段1 长度2 → 贡献 `3`；前缀和 `s = [0, 1, 4]`

查询 `[0, 2]`：
- `left=0` 落在段0，`right=2` 落在段1
- 左不完整段：`a = 1 - 0 = 1` → 贡献 `1`
- 中间完整段：`s[1] - s[1] = 0`
- 右不完整段：`b = 2 - 1 + 1 = 2` → 贡献 `3`
- 总计：`1 + 0 + 3 = 4` ✓