Hard

题目描述

给定一个长度为 n 的整数数组 nums 和一个整数 k。

逆序对是数组中的一对索引 (i, j)，满足 i < j 且 nums[i] > nums[j]。

子数组的逆序对数量是其内部逆序对的数量。

返回所有长度为 k 的子数组中的最小逆序对数量。

示例 1：

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

解释：
我们考虑所有长度为 k = 3 的子数组（下面的索引相对于每个子数组）：
- [3, 1, 2] 有 2 个逆序对：(0, 1) 和 (0, 2)
- [1, 2, 5] 有 0 个逆序对
- [2, 5, 4] 有 1 个逆序对：(1, 2)

所有长度为 3 的子数组中的最小逆序对数量是 0，由子数组 [1, 2, 5] 实现。

示例 2：

输入：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。

示例 3：

输入：nums = [2,1], k = 1
输出：0

解释：
所有长度为 k = 1 的子数组只包含一个元素，所以不可能有逆序对。
因此最小逆序对数量是 0。

约束条件：

  • 1 <= n == nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= n

提示：

  • 将所有数字压缩到范围 1 到 n 的整数
  • 使用树状数组（BIT）来维护数字的计数
  • 当在后面添加元素时，查询有多少元素比它大；当从前面删除元素时，查询有多少元素比它小并相应地更新树

解题思路

这道题要求在滑动窗口内高效地计算逆序对数量。我们需要使用滑动窗口技巧和树状数组来优化计算过程。

核心思路：

  1. 坐标压缩：由于数值范围可能很大（最大10^9），我们需要将所有数字压缩到 1 到 n 的范围内，以便使用树状数组。

  2. 树状数组（Fenwick Tree/BIT）：用于快速查询前缀和，帮助计算逆序对。对于每个位置的数字，我们可以：

    • 查询比当前数字大的元素个数（这些形成逆序对）
    • 更新该数字的出现次数

  3. 滑动窗口策略：

    • 首先计算第一个长度为 k 的窗口的逆序对数量
    • 然后滑动窗口：移除左边元素，添加右边元素
    • 移除元素时：减少对应的逆序对贡献
    • 添加元素时：增加对应的逆序对贡献

  4. 逆序对计算：

    • 添加元素 x 时：查询树状数组中比 x 大的元素个数
    • 移除元素 x 时：查询树状数组中比 x 小的元素个数，这些都曾与 x 构成逆序对

时间复杂度：每个元素的插入和删除都需要 O(log n) 时间，总体为 O(n log n)。

代码实现

class Solution {
public:
    long long minInversionCount(vector<int>& nums, int k) {
        int n = nums.size();
        
        // Coordinate compression
        vector<int> sorted_nums = nums;
        sort(sorted_nums.begin(), sorted_nums.end());
        sorted_nums.erase(unique(sorted_nums.begin(), sorted_nums.end()), sorted_nums.end());
        
        unordered_map<int, int> compress;
        for (int i = 0; i < sorted_nums.size(); i++) {
            compress[sorted_nums[i]] = i + 1;
        }
        
        vector<int> bit(sorted_nums.size() + 1, 0);
        
        auto update = [&](int idx, int delta) {
            for (; idx < bit.size(); idx += idx & -idx) {
                bit[idx] += delta;
            }
        };
        
        auto query = [&](int idx) {
            int sum = 0;
            for (; idx > 0; idx -= idx & -idx) {
                sum += bit[idx];
            }
            return sum;
        };
        
        // Calculate inversions for first window
        long long current_inv = 0;
        for (int i = 0; i < k; i++) {
            int compressed = compress[nums[i]];
            // Count elements greater than current element
            current_inv += query(bit.size() - 1) - query(compressed);
            update(compressed, 1);
        }
        
        long long min_inv = current_inv;
        
        // Slide the window
        for (int i = k; i < n; i++) {
            // Remove the leftmost element
            int left_compressed = compress[nums[i - k]];
            update(left_compressed, -1);
            // Count how many elements in current window are smaller than the removed element
            current_inv -= query(left_compressed - 1);
            
            // Add the rightmost element
            int right_compressed = compress[nums[i]];
            // Count how many elements in current window are greater than the new element
            current_inv += query(bit.size() - 1) - query(right_compressed);
            update(right_compressed, 1);
            
            min_inv = min(min_inv, current_inv);
        }
        
        return min_inv;
    }
};

class Solution:
    def minInversionCount(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # Coordinate compression
        sorted_nums = sorted(set(nums))
        compress = {num: i + 1 for i, num in enumerate(sorted_nums)}
        
        class BIT:
            def __init__(self, size):
                self.size = size
                self.tree = [0] * (size + 1)
            
            def update(self, idx, delta):
                while idx <= self.size:
                    self.tree[idx] += delta
                    idx += idx & (-idx)
            
            def query(self, idx):
                result = 0
                while idx > 0:
                    result += self.tree[idx]
                    idx -= idx & (-idx)
                return result
        
        bit = BIT(len(sorted_nums))
        
        # Calculate inversions for first window
        current_inv = 0
        for i in range(k):
            compressed = compress[nums[i]]
            # Count elements greater than current element
            current_inv += bit.query(len(sorted_nums)) - bit.query(compressed)
            bit.update(compressed, 1)
        
        min_inv = current_inv
        
        # Slide the window
        for i in range(k, n):
            # Remove the leftmost element
            left_compressed = compress[nums[i - k]]
            bit.update(left_compressed, -1)
            # Count how many elements in current window are smaller than the removed element
            current_inv -= bit.query(left_compressed - 1)
            
            # Add the rightmost element
            right_compressed = compress[nums[i]]
            # Count how many elements in current window are greater than the new element
            current_inv += bit.query(len(sorted_nums)) - bit.query(right_compressed)
            bit.update(right_compressed, 1)
            
            min_inv = min(min_inv, current_inv)
        
        return min_inv

public class Solution {
    public long MinInversionCount(int[] nums, int k) {
        int n = nums.Length;
        
        // Coordinate compression
        var sortedNums = nums.Distinct().OrderBy(x => x).ToArray();
        var compress = new Dictionary<int, int>();
        for (int i = 0; i < sortedNums.Length; i++) {
            compress[sortedNums[i]] = i + 1;
        }
        
        var bit = new int[sortedNums.Length + 1];
        
        void Update(int idx, int delta) {
            for (; idx < bit.Length; idx += idx & -idx) {
                bit[idx] += delta;
            }
        }
        
        int Query(int idx) {
            int sum = 0;
            for (; idx > 0; idx -= idx & -idx) {
                sum += bit[idx];
            }
            return sum;
        }
        
        // Calculate inversions for first window
        long currentInv = 0;
        for (int i = 0; i < k; i++) {
            int compressed = compress[nums[i]];
            // Count elements greater than current element
            currentInv += Query(bit.Length - 1) - Query(compressed);
            Update(compressed, 1);
        }
        
        long minInv = currentInv;
        
        // Slide the window
        for (int i = k; i < n; i++) {
            // Remove the leftmost element
            int leftCompressed = compress[nums[i - k]];
            Update(leftCompressed, -1);
            // Count how many elements in current window are smaller than the removed element
            currentInv -= Query(leftCompressed - 1);
            
            // Add the rightmost element
            int rightCompressed = compress[nums[i]];
            // Count how many elements in current window are greater than the new element
            currentInv += Query(bit.Length - 1) - Query(rightCompressed);
            Update(rightCompressed, 1);
            
            minInv = Math.Min(minInv, currentInv);
        }
        
        return minInv;
    }
}

var minInversionCount = function(nums, k) {
    const n = nums.length;
    
    // Coordinate compression
    const sortedNums = [...new Set(nums)].sort((a, b) => a - b);
    const compress = new Map();
    for (let i = 0; i < sortedNums.length; i++) {
        compress.set(sortedNums[i], i + 1);
    }
    
    const bit = new Array(sortedNums.length + 1).fill(0);
    
    const update = (idx, delta) => {
        for (; idx < bit.length; idx += idx & -idx) {
            bit[idx] += delta;
        }
    };
    
    const query = (idx) => {
        let sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += bit[idx];
        }
        return sum;
    };
    
    // Calculate inversions for first window
    let currentInv = 0;
    for (let i = 0; i < k; i++) {
        const compressed = compress.get(nums[i]);
        // Count elements greater than current element
        currentInv += query(bit.length - 1) - query(compressed);
        update(compressed, 1);
    }
    
    let minInv = currentInv;
    
    // Slide the window
    for (let i = k; i < n; i++) {
        // Remove the leftmost element
        const leftCompressed = compress.get(nums[i - k]);
        update(leftCompressed, -1);
        // Count how many elements in current window are smaller than the removed element
        currentInv -= query(leftCompressed - 1);
        
        // Add the rightmost element
        const rightCompressed = compress.get(nums[i]);
        // Count how many elements in current window are greater than the new element
        currentInv += query(bit.length - 1) - query(rightCompressed);
        update(rightCompressed, 1);
        
        minInv = Math.min(minInv, currentInv);
    }
    
    return minInv;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，其中 n 为数组长度。坐标压缩需要 O(n log n)，每次树状数组操作为 O(log n)，总共需要 n 次操作
空间复杂度O(n)，用于存储压缩后的坐标映射和树状数组