这道题是滑动窗口结合树状数组Fenwick Tree 的经典应用。核心思路是随着窗口滑动增量更新逆序对数量从而在 O(n log n) 时间内找到所有固定长度子数组的最小逆序对数。核心思路1. 离散化坐标压缩nums[i] 最大可达 1e9直接开数组会超内存。需要先排序去重将每个数映射为 1 到 n 的排名。2. 树状数组维护窗口树状数组 bit 存储当前窗口中每个值的出现次数支持· add(idx, delta)更新计数 O(log n)· presum(idx)查询小于等于 idx 的个数 O(log n)3. 滑动窗口维护逆序对遍历 nums 逐个将元素 nums[i] 加入窗口· 新增逆序对窗口大小 - 小于等于当前元素的个数即窗口中比 nums[i] 大的元素数量。· 移除左边界当窗口长度 k 时移除 nums[i-k]。其减少的逆序对等于窗口中比它小的元素数量即 presum(value - 1)。· 记录答案当 i k-1 时窗口已满更新最小值。Java 实现javaimport java.util.Arrays;class Solution {public long minInversionCount(int[] nums, int k) {int n nums.length;// 1. 离散化int[] sorted nums.clone();Arrays.sort(sorted);for (int i 0; i n; i) {nums[i] Arrays.binarySearch(sorted, nums[i]) 1;}// 2. 树状数组BIT bit new BIT(n);long invCount 0;long ans Long.MAX_VALUE;for (int i 0; i n; i) {int val nums[i];// 加入新元素统计新增逆序对// 当前窗口已有 i 个元素但最多 k 个有效int windowSize Math.min(i, k - 1);// 窗口中大于 val 的元素个数 窗口大小 - 小于等于 val 的个数invCount windowSize - bit.query(val);bit.update(val, 1);// 窗口未满继续if (i k - 1) continue;// 窗口已满更新答案ans Math.min(ans, invCount);// 移除左边界元素准备滑动int leftVal nums[i - k 1];// 移除时减少的逆序对 窗口中比 leftVal 小的元素个数invCount - bit.query(leftVal - 1);bit.update(leftVal, -1);}return ans;}// 树状数组Fenwick Treeprivate static class BIT {int[] tree;BIT(int n) {tree new int[n 1];}void update(int idx, int delta) {while (idx tree.length) {tree[idx] delta;idx idx -idx;}}int query(int idx) {int sum 0;while (idx 0) {sum tree[idx];idx - idx -idx;}return sum;}}}复杂度分析· 时间复杂度O(n log n)主要来自离散化排序和每次窗口操作的树状数组更新与查询。· 空间复杂度O(n)用于存储树状数组和排序副本。
