以下是 LeetCode 3768 的 Python3 实现采用滑动窗口 离散化 树状数组Fenwick Treepythonfrom typing import Listclass Solution:def minInversionCount(self, nums: List[int], k: int) - int:n len(nums)if k 1:return 0# ---------- 1. 离散化 ----------# 将原数值映射到 1..m 的排名m 为不同元素个数sorted_vals sorted(set(nums))rank {v: i 1 for i, v in enumerate(sorted_vals)}m len(sorted_vals)arr [rank[x] for x in nums]# ---------- 2. 树状数组 (Fenwick Tree) ----------class BIT:def __init__(self, size: int):self.tree [0] * (size 1)self.size sizedef update(self, idx: int, delta: int) - None:while idx self.size:self.tree[idx] deltaidx idx -idxdef query(self, idx: int) - int:查询前缀和 [1..idx]s 0while idx 0:s self.tree[idx]idx - idx -idxreturn sbit BIT(m)inv_count 0ans float(inf)# ---------- 3. 滑动窗口 ----------for i in range(n):val arr[i]# 当前窗口已有元素个数尚未加入新元素前window_size min(i, k - 1)# 新增逆序对 窗口中大于 val 的元素个数# 窗口大小 - 窗口中 val 的元素个数inv_count window_size - bit.query(val)# 将 val 加入窗口bit.update(val, 1)# 当窗口长度达到 k 时if i k - 1:ans min(ans, inv_count)# 移除左边界元素准备滑动left_val arr[i - k 1]# 移除时减少的逆序对 窗口中比 left_val 小的元素个数inv_count - bit.query(left_val - 1)bit.update(left_val, -1)return int(ans)测试示例python# 测试sol Solution()print(sol.minInversionCount([3, 1, 2, 4], 2)) # 输出: 0print(sol.minInversionCount([2, 3, 1], 3)) # 输出: 2print(sol.minInversionCount([1, 2, 3, 4], 2)) # 输出: 0算法详解核心思想随着窗口向右滑动每次只对窗口新增的元素和移除的元素进行逆序对的增量更新避免每次重新计算整个窗口。1. 离散化· nums[i] 范围可能很大1e9直接开数组会超内存· 使用 rank 将每个数映射到 1 ~ m 的排名2. 树状数组维护· tree[idx] 记录当前窗口中值为 idx 的元素个数· query(idx)查询窗口内值 ≤ idx 的元素个数3. 滑动窗口逻辑操作 逆序对变化 代码加入 val 增加窗口中比 val 大的元素个数 window_size - bit.query(val)移除 left_val 减少窗口中比 left_val 小的元素个数 bit.query(left_val - 1)复杂度分析· 时间复杂度O(n log n)· 离散化排序O(n log n)· 滑动窗口每个元素更新和查询树状数组各一次O(log n)· 空间复杂度O(n)· 树状数组O(m) ≤ O(n)· 离散化映射O(m)关键边界处理· k 1每个子数组长度为 1逆序对数为 0直接返回· 重复元素离散化后相等元素排名相同query(val) 会包含相等元素正确计算严格大于的新增逆序对