3691. 最大子数组值总和 II

Hard

题目描述

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

你必须从 nums 中选择恰好 k 个不同的非空子数组 nums[l..r]。子数组可以重叠，但完全相同的子数组（相同的 l 和 r）不能选择超过一次。

子数组 nums[l..r] 的值定义为：max(nums[l..r]) - min(nums[l..r])。

总值是所有选择子数组的值的总和。

返回你能实现的最大总值。

示例 1：

输入：nums = [1,3,2], k = 2
输出：4
解释：
一种最优方法是：
- 选择 nums[0..1] = [1, 3]。最大值是 3，最小值是 1，值为 3 - 1 = 2。
- 选择 nums[0..2] = [1, 3, 2]。最大值是 3，最小值是 1，值为 3 - 1 = 2。
总和为 2 + 2 = 4。

示例 2：

输入：nums = [4,2,5,1], k = 3
输出：12
解释：
一种最优方法是：
- 选择 nums[0..3] = [4, 2, 5, 1]。最大值是 5，最小值是 1，值为 5 - 1 = 4。
- 选择 nums[1..3] = [2, 5, 1]。最大值是 5，最小值是 1，值为 4。
- 选择 nums[2..3] = [5, 1]。最大值是 5，最小值是 1，值为 4。
总和为 4 + 4 + 4 = 12。

约束条件：

1 <= n == nums.length <= 5 * 10^4
0 <= nums[i] <= 10^9
1 <= k <= min(10^5, n * (n + 1) / 2)

提示：

对于固定的 l，序列 v(l,r) = max(nums[l..r]) - min(nums[l..r]) 随着 r 向左移动是非递增的。
构建 RMQ（稀疏表）用于区间最大/最小值查询，使每个 v(l,r) 可在 O(1) 时间内查询。
使用最大堆存储所有 l 的 v(l,n-1)；弹出最大的 k 次，弹出 (l,r) 后，如果 r > l 则推入 (l,r-1)。

解题思路

这是一个贪心问题，关键观察是：对于固定的左端点 l，随着右端点 r 向左移动（减小），子数组的值 max(nums[l..r]) - min(nums[l..r]) 是非递增的。

解题思路：

预处理：使用稀疏表（Sparse Table）构建 RMQ 数据结构，支持 O(1) 时间查询任意区间的最大值和最小值。
贪心策略：使用最大堆维护所有可能的子数组值。初始时，将每个左端点 l 对应的最长子数组 [l, n-1] 的值加入堆中。
迭代选择：重复 k 次：
- 从堆中弹出当前最大的子数组值
- 将该值累加到结果中
- 如果该子数组可以缩短（右端点向左移动），将缩短后的子数组值加入堆中
优化细节：由于子数组值的单调性，我们只需要从每个左端点开始，逐步缩短子数组，确保每次都选择当前可用的最大值。

这种方法确保我们始终选择当前可用的最大子数组值，直到选择了 k 个不同的子数组。

代码实现

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        int n = nums.size();
        
        // Build sparse table for range max and min queries
        int logN = 32 - __builtin_clz(n);
        vector<vector<int>> maxST(logN, vector<int>(n));
        vector<vector<int>> minST(logN, vector<int>(n));
        
        for (int i = 0; i < n; i++) {
            maxST[0][i] = minST[0][i] = nums[i];
        }
        
        for (int j = 1; j < logN; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                maxST[j][i] = max(maxST[j-1][i], maxST[j-1][i + (1 << (j-1))]);
                minST[j][i] = min(minST[j-1][i], minST[j-1][i + (1 << (j-1))]);
            }
        }
        
        auto query = [&](int l, int r) -> long long {
            int len = r - l + 1;
            int log = 31 - __builtin_clz(len);
            int maxVal = max(maxST[log][l], maxST[log][r - (1 << log) + 1]);
            int minVal = min(minST[log][l], minST[log][r - (1 << log) + 1]);
            return maxVal - minVal;
        };
        
        // Priority queue to store (value, left, right)
        priority_queue<tuple<long long, int, int>> pq;
        
        // Initialize with all subarrays starting at each position
        for (int l = 0; l < n; l++) {
            pq.push({query(l, n - 1), l, n - 1});
        }
        
        long long result = 0;
        for (int i = 0; i < k; i++) {
            auto [val, l, r] = pq.top();
            pq.pop();
            result += val;
            
            if (r > l) {
                pq.push({query(l, r - 1), l, r - 1});
            }
        }
        
        return result;
    }
};

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        import heapq
        import math
        
        n = len(nums)
        
        # Build sparse table for range max and min queries
        log_n = n.bit_length()
        max_st = [[0] * n for _ in range(log_n)]
        min_st = [[0] * n for _ in range(log_n)]
        
        for i in range(n):
            max_st[0][i] = min_st[0][i] = nums[i]
        
        for j in range(1, log_n):
            for i in range(n - (1 << j) + 1):
                max_st[j][i] = max(max_st[j-1][i], max_st[j-1][i + (1 << (j-1))])
                min_st[j][i] = min(min_st[j-1][i], min_st[j-1][i + (1 << (j-1))])
        
        def query(l, r):
            length = r - l + 1
            log = length.bit_length() - 1
            max_val = max(max_st[log][l], max_st[log][r - (1 << log) + 1])
            min_val = min(min_st[log][l], min_st[log][r - (1 << log) + 1])
            return max_val - min_val
        
        # Priority queue (max heap) to store (-value, left, right)
        pq = []
        
        # Initialize with all subarrays starting at each position
        for l in range(n):
            heapq.heappush(pq, (-query(l, n - 1), l, n - 1))
        
        result = 0
        for _ in range(k):
            neg_val, l, r = heapq.heappop(pq)
            result += -neg_val
            
            if r > l:
                heapq.heappush(pq, (-query(l, r - 1), l, r - 1))
        
        return result

public class Solution {
    public long MaxTotalValue(int[] nums, int k) {
        int n = nums.Length;
        
        // Build sparse table for range max and min queries
        int logN = 32 - LeadingZeroCount(n);
        int[,] maxST = new int[logN, n];
        int[,] minST = new int[logN, n];
        
        for (int i = 0; i < n; i++) {
            maxST[0, i] = minST[0, i] = nums[i];
        }
        
        for (int j = 1; j < logN; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                maxST[j, i] = Math.Max(maxST[j-1, i], maxST[j-1, i + (1 << (j-1))]);
                minST[j, i] = Math.Min(minST[j-1, i], minST[j-1, i + (1 << (j-1))]);
            }
        }
        
        long Query(int l, int r) {
            int len = r - l + 1;
            int log = 31 - LeadingZeroCount(len);
            int maxVal = Math.Max(maxST[log, l], maxST[log, r - (1 << log) + 1]);
            int minVal = Math.Min(minST[log, l], minST[log, r - (1 << log) + 1]);
            return maxVal - minVal;
        }
        
        // Priority queue to store (value, left, right)
        var pq = new PriorityQueue<(long val, int l, int r), long>();
        
        // Initialize with all subarrays starting at each position
        for (int l = 0; l < n; l++) {
            long val = Query(l, n - 1);
            pq.Enqueue((val, l, n - 1), -val); // Negative for max heap
        }
        
        long result = 0;
        for (int i = 0; i < k; i++) {
            var (val, l, r) = pq.Dequeue();
            result += val;
            
            if (r > l) {
                long newVal = Query(l, r - 1);
                pq.Enqueue((newVal, l, r - 1), -newVal);
            }
        }
        
        return result;
    }
    
    private int LeadingZeroCount(int value) {
        if (value == 0) return 32;
        int count = 0;
        if (value <= 0x0000FFFF) { count += 16; value <<= 16; }
        if (value <= 0x00FFFFFF) { count += 8; value <<= 8; }
        if (value <= 0x0FFFFFFF) { count += 4; value <<= 4; }
        if (value <= 0x3FFFFFFF) { count += 2; value <<= 2; }
        if (value <= 0x7FFFFFFF) { count += 1; }
        return count;
    }
}

var maxTotalValue = function(nums, k) {
    const n = nums.length;
    
    // Build sparse table for range max and min queries
    const logN = Math.ceil(Math.log2(n)) + 1;
    const maxST = Array(logN).fill().map(() => Array(n).fill(0));
    const minST = Array(logN).fill().map(() => Array(n).fill(0));
    
    for (let i = 0; i < n; i++) {
        maxST[0][i] = minST[0][i] = nums[i];
    }
    
    for (let j = 1; j < logN; j++) {
        for (let i = 0; i + (1 << j) <= n; i++) {
            maxST[j][i] = Math.max(maxST[j-1][i], maxST[j-1][i + (1 << (j-1))]);
            minST[j][i] = Math.min(minST[j-1][i], minST[j-1][i + (1 << (j-1))]);
        }
    }
    
    const query = (l, r) => {
        const len = r - l + 1;
        const log = Math.floor(Math.log2(len));
        const maxVal = Math.max(maxST[log][l], maxST[log][r - (1 << log) + 1]);
        const minVal = Math.min(minST[log][l], minST[log][r - (1 << log) + 1]);
        return maxVal - minVal;
    };
    
    // Priority queue simulation using array and manual sorting
    const pq = [];
    
    // Initialize with all subarrays starting at each position
    for (let l = 0; l < n; l++) {
        pq.push([query(l, n - 1), l, n - 1]);
    }
    
    let result = 0;
    for (let i = 0; i < k; i++) {
        // Sort to get maximum value (simulate max heap)
        pq.sort((a, b) => b[0] - a[0]);
        const [val, l, r] = pq.shift();
        result += val;
        
        if (r > l) {
            pq.push([query(l, r - 1), l, r - 1]);
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	C++	Python	C#	JavaScript
时间复杂度	O(n log n + k log n)	O(n log n + k log n)	O(n log n + k log n)	O(n log n + k² log n)
空间复杂度	O(n log n)	O(n log n)	O(n log n)	O(n log n)

说明：

预处理稀疏表需要 O(n log n) 时间和空间
选择

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析