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 代码javaimport java.util.ArrayList;import java.util.List;class Solution {public long[] countStableSubarrays(int[] nums, int[][] queries) {// seg: 每段非降序子数组的起始位置ListInteger seg new ArrayList();// s: 前缀和s[i] 表示前 i 个完整段中稳定子数组的总数ListLong s new ArrayList();s.add(0L);int l 0;int n nums.length;for (int r 0; r n; r) {// 当遇到下降时nums[r] nums[r1]或者到达末尾结束当前段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(ListInteger 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]- left0 落在段0right2 落在段1- 左不完整段a 1 - 0 1 → 贡献 1- 中间完整段s[1] - s[1] 0- 右不完整段b 2 - 1 1 2 → 贡献 3- 总计1 0 3 4 ✓