2026-04-19: 固定长度子数组中的最小逆序对数目。用go语言, 给你

2026-04-19：固定长度子数组中的最小逆序对数目。用go语言，给你一个整数数组 nums（长度为 n）和一个整数 k。所谓“逆序对”，指的是在数组中下标满足 i nums[j] 的任意一对位置 (i, j)。

对某个连续片段（即子数组）而言，统计它内部所有满足上述条件的逆序对数量，这个数量就是该子数组的“逆序对数量”。

现在考虑 nums 中所有长度恰好为 k 的连续子数组，要求找出其中逆序对数量的最小值并返回。

1

1

1

输入：nums = [5,3,2,1], k = 4。

输出：6。

解释：

只有一个长度为 k = 4 的子数组：[5, 3, 2, 1]。

在该子数组中，逆序对为：(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), 和 (2, 3)。

逆序对总数为 6，因此最小逆序对数量是 6。

题目来自力扣3768。

大体步骤如下：

一、核心前置知识铺垫

1. 逆序对：子数组内满足 inums[j] 的数对，我们要统计每个长度为k的连续子数组的逆序对总数，找最小值。

2. 滑动窗口：数组中所有长度为k的连续子数组，本质是一个固定大小为k的窗口从左向右滑动，每次移动一位。

3. 树状数组：高效完成单点更新和前缀和查询的数据结构，用来快速统计逆序对（避免暴力枚举超时）。

4. 离散化：因为数组元素值最大可达1e9，无法直接用树状数组存储，所以把原数组的值映射为连续的小整数（1,2,3...）。

二、分步骤详细执行过程

步骤1：离散化处理（压缩数值范围）

原数组：[5, 3, 2, 1]

1. 克隆原数组并排序、去重，得到排序去重数组：[1,2,3,5]

2. 把原数组的每个值，替换为它在排序数组中的位置+1（树状数组下标从1开始）：

• 5 → 4

• 3 → 3

• 2 → 2

• 1 → 1

3. 离散化后的数组：[4, 3, 2, 1]

作用：把超大数值变成1~4的连续整数，适配树状数组。

步骤2：初始化核心变量

1. 初始化树状数组：长度为 离散化后最大值+1 = 5，初始值全0。

2. 逆序对计数器 inv = 0：记录当前窗口的逆序对总数。

3. 答案变量 ans = 最大值：存储所有窗口的最小逆序对。

4. 固定窗口大小：k=4。

步骤3：滑动窗口遍历数组（逐个元素处理）

我们遍历离散化后的数组 [4,3,2,1]，每一步分为：元素入窗口 → 计算逆序对 → 窗口成型则更新答案 → 元素出窗口。

第1次遍历（处理第一个元素：4）

1. 元素入窗口：把数字4加入树状数组，树状数组标记4的位置计数+1。

2. 累加逆序对：当前窗口内比4大的数字个数为0，逆序对总数 inv = 0。

3. 窗口判断：当前窗口长度=1

第2次遍历（处理第二个元素：3）

1. 元素入窗口：把数字3加入树状数组，树状数组标记3的位置计数+1。

2. 累加逆序对：当前窗口内比3大的数字只有4，逆序对总数 inv = 1。

3. 窗口判断：当前窗口长度=2

第3次遍历（处理第三个元素：2）

1. 元素入窗口：把数字2加入树状数组，树状数组标记2的位置计数+1。

2. 累加逆序对：当前窗口内比2大的数字有4、3，逆序对总数 inv = 1+2=3。

3. 窗口判断：当前窗口长度=3

第4次遍历（处理第四个元素：1）

1. 元素入窗口：把数字1加入树状数组，树状数组标记1的位置计数+1。

2. 累加逆序对：当前窗口内比1大的数字有4、3、2，逆序对总数 inv = 3+3=6。

3. 窗口判断：窗口长度=4，刚好形成第一个有效窗口。

4. 更新最小答案：当前逆序对总数6是最小值，ans=6。

5. 元素出窗口：窗口左侧第一个元素4移出树状数组，树状数组标记4的位置计数-1。

6. 修正逆序对：减去移出元素4带来的逆序对数量，逆序对总数更新。

步骤4：遍历结束，输出结果

整个数组遍历完成，唯一的有效窗口逆序对总数为6，最终返回6。

三、关键逻辑补充说明

1. 元素入窗口时：用树状数组快速查询当前窗口中比新元素大的数字个数，直接累加到逆序对总数。

2. 窗口成型后：用当前逆序对总数更新最小值。

3. 元素出窗口时：用树状数组快速查询比移出元素小的数字个数，从逆序对总数中减去（因为这个元素离开了窗口，它贡献的逆序对也要删掉）。

4. 提前终止：如果逆序对总数变为0（理论最小值），直接结束计算，优化效率。

四、时间复杂度分析

1. 离散化：排序+去重+映射，时间复杂度为 O(n log n)。

2. 滑动窗口遍历：遍历n个元素，每个元素执行2次树状数组操作（更新+查询），树状数组单次操作复杂度为 O(log m)（m是离散化后的数值范围，m≤n）。

总遍历复杂度：O(n log n)。

总的时间复杂度：O(n log n)

（这是处理n≤1e5数据的最优复杂度，能完美通过题目限制）

五、额外空间复杂度分析

额外空间指除输入数组外，代码主动开辟的空间：

1. 离散化用的排序数组：O(n)。

2. 树状数组：O(n)。

3. 其他临时变量：O(1)。

总的额外空间复杂度：O(n)

总结

1. 执行流程：离散化压缩数值 → 滑动窗口遍历元素 → 树状数组高效统计逆序对 → 维护最小逆序对数量；

2. 时间复杂度：O(n log n)，适配1e5规模数据；

3. 额外空间复杂度：O(n)。

Go完整代码如下：

package main

import (

"fmt"

"math"

"slices"

"sort"

)

type fenwick []int

func (t fenwick) update(i, val int) {

for ; i

t[i] += val

}

}

func (t fenwick) pre(i int) (res int) {

for ; i > 0; i &= i - 1 {

res += t[i]

}

return

}

func minInversionCount(nums []int, k int)int64 {

// 离散化

sorted := slices.Clone(nums)

slices.Sort(sorted)

sorted = slices.Compact(sorted)

for i, x := range nums {

nums[i] = sort.SearchInts(sorted, x) + 1// 树状数组下标从 1 开始

}

t := make(fenwick, len(sorted)+1)

inv := 0

ans := math.MaxInt

for i, in := range nums {

// 1. 入

t.update(in, 1)

inv += min(i+1, k) - t.pre(in) // 窗口大小 - (x 的元素个数)

left := i + 1 - k

if left

continue

}

// 2. 更新答案

ans = min(ans, inv)

if ans == 0 { // 已经最小了，无需再计算

break

}

// 3. 出

out := nums[left]

inv -= t.pre(out - 1) //

t.update(out, -1)

}

returnint64(ans)

}

func main {

nums := []int{5, 3, 2, 1}

k := 4

result := minInversionCount(nums, k)

fmt.Println(result)

}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

class Fenwick:

def __init__(self, n: int):

self.n = n

self.bit = [0] * (n + 1)

def update(self, i: int, val: int) -> None:

"""将位置i增加val（i从1开始）"""

while i

self.bit[i] += val

i += i & -i

def pre(self, i: int) -> int:

"""前缀和：1到i的和"""

res = 0

while i > 0:

res += self.bit[i]

i &= i - 1

return res

def min_inversion_count(nums: List[int], k: int) -> int:

"""

计算所有长度为k的子数组中逆序对的最小值

"""

# 离散化

sorted_nums = sorted(set(nums))

# 映射到1,2,3,...（树状数组下标从1开始）

num_to_idx = {val: idx + 1for idx, val in enumerate(sorted_nums)}

nums = [num_to_idx[x] for x in nums]

# 树状数组

bit = Fenwick(len(sorted_nums))

inv = 0 # 当前窗口的逆序对数

ans = float('inf')

for i, num in enumerate(nums):

# 1. 入：将当前元素加入窗口

bit.update(num, 1)

# 窗口大小 = min(i+1, k)

window_size = min(i + 1, k)

# 大于num的元素个数 = 窗口大小 - 小于等于num的元素个数

inv += window_size - bit.pre(num)

left = i + 1 - k

if left

# 尚未形成第一个窗口

continue

# 2. 更新答案

ans = min(ans, inv)

if ans == 0:

# 已经是最小值，无需继续计算

break

# 3. 出：移除窗口最左边的元素

out_num = nums[left]

# 小于out_num的元素个数（这些元素与out_num构成逆序对）

inv -= bit.pre(out_num - 1)

bit.update(out_num, -1)

returnint(ans)

def main:

nums = [5, 3, 2, 1]

k = 4

result = min_inversion_count(nums, k)

print(result)

if __name__ == "__main__":

main

C++完整代码如下：

#include

#include

#include

#include

using namespace std;

class Fenwick {

private:

vector bit;

public:

Fenwick(int n) : bit(n + 1, 0) {}

void update(int i, int val) {

for (; i

bit[i] += val;

}

}

int pre(int i) {

int res = 0;

for (; i > 0; i &= i - 1) {

res += bit[i];

}

return res;

}

};

long long minInversionCount(vector& nums, int k) {

// 离散化

vector sorted = nums;

sort(sorted.begin, sorted.end);

sorted.erase(unique(sorted.begin, sorted.end), sorted.end);

for (int i = 0; i

nums[i] = lower_bound(sorted.begin, sorted.end, nums[i]) - sorted.begin + 1; // 树状数组下标从1开始

}

Fenwick bit(sorted.size);

int inv = 0;

int ans = INT_MAX;

for (int i = 0; i

int in = nums[i];

// 1. 入

bit.update(in, 1);

inv += min(i + 1, k) - bit.pre(in); // 窗口大小 - (x的元素个数)

int left = i + 1 - k;

if (left

continue;

}

// 2. 更新答案

ans = min(ans, inv);

if (ans == 0) { // 已经最小了，无需再计算

break;

}

// 3. 出

int out = nums[left];

inv -= bit.pre(out - 1); //

bit.update(out, -1);

}

return (long long)ans;

}

int main {

vector nums = {5, 3, 2, 1};

int k = 4;

long long result = minInversionCount(nums, k);

cout

return0;

}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。

欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。