2026-02-19：最大子数组总值Ⅱ。用go语言，给定长度为 n 的整数数组 nums 和一个整数 k。你要从数组中挑出恰好 k 个互不相同的非空连续区

福大大架构师每日一题

发布于 2026-03-04 19:09:00

900

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-02-19：最大子数组总值Ⅱ。用go语言，给定长度为 n 的整数数组 nums 和一个整数 k。你要从数组中挑出恰好 k 个互不相同的非空连续区间（允许区间彼此重叠，但不能重复选取同一对左右端点确定的区间）。

每个区间的得分定义为该区间内元素的最大值减去最小值。总得分为所选 k 个区间得分的累计和。

求可以获得的最大总得分。说明：“连续区间”指由若干相邻元素组成且非空的数组片段。

1 <= n == nums.length <= 50000。

0 <= nums[i] <= 1000000000。

1 <= k <= min(100000, n * (n + 1) / 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。

题目来自力扣3691。

算法过程描述

1. 数据结构准备

• 构建**稀疏表（Sparse Table）**用于快速查询任意区间 [l, r] 的最大值和最小值
• 构建**最大堆（优先队列）**用于存储候选区间，堆顶是得分最大的区间

2. 初始化过程

• 对于数组 nums，生成所有以 0 为左边界的子数组：
- • [0,0]、[0,1]、[0,2]、...、[0,n-1]
• 计算每个子数组的差值（最大值-最小值）
• 将这些子数组作为 Item（包含左边界 l、右边界 r、差值 val）放入最大堆

3. 迭代选择过程

重复以下步骤直到选满 k 个区间或堆为空：

1. 从堆顶取出当前差值最大的区间 item
2. 将该区间的差值累加到总分 sum
3. 检查是否可以生成新的候选区间：如果 item.l+1 <= item.r，说明可以将左边界向右移动一位，得到新区间 [item.l+1, item.r]
4. 计算新区间的差值，并将其加入堆中
5. 重复步骤 1-4，直到选出 k 个区间

4. 示例推演（nums = [4,2,5,1], k = 3）

初始化：将以下区间加入堆

• [0,0] = 0
• [0,1] = max(4,2)-min(4,2) = 4-2 = 2
• [0,2] = max(4,2,5)-min(4,2,5) = 5-2 = 3
• [0,3] = max(4,2,5,1)-min(4,2,5,1) = 5-1 = 4

堆中元素按差值降序：[0,3]=4, [0,2]=3, [0,1]=2, [0,0]=0

第一次选择：

• 弹出 [0,3]（差值4），总分 = 4
• 生成新区间 [1,3]，计算差值 = max(2,5,1)-min(2,5,1) = 5-1 = 4，加入堆

堆状态：[1,3]=4, [0,2]=3, [0,1]=2, [0,0]=0

第二次选择：

• 弹出 [1,3]（差值4），总分 = 4+4 = 8
• 生成新区间 [2,3]，计算差值 = max(5,1)-min(5,1) = 5-1 = 4，加入堆

堆状态：[2,3]=4, [0,2]=3, [0,1]=2, [0,0]=0

第三次选择：

• 弹出 [2,3]（差值4），总分 = 8+4 = 12
• 生成新区间 [3,3]（差值0），加入堆

已选满3个区间，停止

最终总分 = 12

时间复杂度分析

• 稀疏表构建：O(n log n)
• 初始化堆：O(n log n)（n 个初始区间入堆）
• 每次堆操作：O(log n)（弹出和推入）
• 总操作次数：O(k + n)（初始 n 个区间 + 最多 k 次生成新区间）
• 总时间复杂度：O(n log n + k log n)

空间复杂度分析

• 稀疏表：O(n log n) 存储
• 堆：最多存储 O(n + k) 个区间
• 总额外空间复杂度：O(n log n + k)

其中 n 是数组长度，k 是需要选择的区间个数。

Go完整代码如下：

package main

import (
    "container/heap"
    "fmt"
    "math/bits"
)

// ST 稀疏表，用于快速查询区间最大值和最小值
type ST struct {
    stMin [][]int// 最小值表
    stMax [][]int// 最大值表
}

// NewST 创建新的稀疏表
func NewST(arr []int) *ST {
    n := len(arr)
    k := bits.Len32(uint32(n)) // 计算需要的层数
    stMin := make([][]int, n)
    stMax := make([][]int, n)

    // 初始化第0层
    for i := 0; i < n; i++ {
        stMin[i] = make([]int, k)
        stMax[i] = make([]int, k)
        stMin[i][0] = arr[i]
        stMax[i][0] = arr[i]
    }

    // 构建稀疏表
    for j := 1; (1 << j) <= n; j++ {
        for i := 0; i+(1<<j) <= n; i++ {
            stMin[i][j] = min(stMin[i][j-1], stMin[i+(1<<(j-1))][j-1])
            stMax[i][j] = max(stMax[i][j-1], stMax[i+(1<<(j-1))][j-1])
        }
    }

    return &ST{
        stMin: stMin,
        stMax: stMax,
    }
}

// Query 查询区间[l, r]的最大值与最小值之差
func (st *ST) Query(l, r int) int {
    k := 31 - bits.LeadingZeros32(uint32(r-l+1))
    // 区间最大值
    maxVal := max(st.stMax[l][k], st.stMax[r-(1<<k)+1][k])
    // 区间最小值
    minVal := min(st.stMin[l][k], st.stMin[r-(1<<k)+1][k])
    return maxVal - minVal
}

// Item 优先队列中的元素
type Item struct {
    l   int// 左边界
    r   int// 右边界
    val int// 区间差值
}

// PriorityQueue 优先队列，按差值降序排列
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { returnlen(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    // 注意：这里使用降序，因为我们要取最大的差值
    return pq[i].val > pq[j].val
}
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

// maxTotalValue 计算前k个最大子数组差值之和
func maxTotalValue(nums []int, k int)int64 {
    st := NewST(nums)
    n := len(nums)

    // 创建优先队列
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    // 将所有以0为左边界的子数组加入优先队列
    for i := 0; i < n; i++ {
        item := &Item{
            l:   0,
            r:   i,
            val: st.Query(0, i),
        }
        heap.Push(&pq, item)
    }

    var sum int64 = 0

    // 取前k个最大的差值
    for k > 0 && pq.Len() > 0 {
        // 取出当前最大的
        item := heap.Pop(&pq).(*Item)
        sum += int64(item.val)

        // 如果左边界还可以右移，将新的子数组加入队列
        if item.l+1 <= item.r {
            newItem := &Item{
                l:   item.l + 1,
                r:   item.r,
                val: st.Query(item.l+1, item.r),
            }
            heap.Push(&pq, newItem)
        }

        k--
    }

    return sum
}

func min(a, b int)int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int)int {
    if a > b {
        return a
    }
    return b
}

func main() {
    nums := []int{4, 2, 5, 1}
    k := 3
    result := maxTotalValue(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

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

import heapq
import math

class ST:
    """稀疏表，用于快速查询区间最大值和最小值"""
    
    def __init__(self, arr):
        """创建新的稀疏表"""
        n = len(arr)
        k = (n).bit_length()  # 计算需要的层数
        
        # 初始化第0层
        self.st_min = [[0] * k for _ in range(n)]
        self.st_max = [[0] * k for _ in range(n)]
        
        for i in range(n):
            self.st_min[i][0] = arr[i]
            self.st_max[i][0] = arr[i]
        
        # 构建稀疏表
        j = 1
        while (1 << j) <= n:
            for i in range(n - (1 << j) + 1):
                self.st_min[i][j] = min(
                    self.st_min[i][j-1], 
                    self.st_min[i + (1 << (j-1))][j-1]
                )
                self.st_max[i][j] = max(
                    self.st_max[i][j-1], 
                    self.st_max[i + (1 << (j-1))][j-1]
                )
            j += 1
    
    def query(self, l, r):
        """查询区间[l, r]的最大值与最小值之差"""
        k = (r - l + 1).bit_length() - 1
        # 区间最大值
        max_val = max(
            self.st_max[l][k], 
            self.st_max[r - (1 << k) + 1][k]
        )
        # 区间最小值
        min_val = min(
            self.st_min[l][k], 
            self.st_min[r - (1 << k) + 1][k]
        )
        return max_val - min_val

class Item:
    """优先队列中的元素"""
    
    def __init__(self, l, r, val):
        self.l = l  # 左边界
        self.r = r  # 右边界
        self.val = val  # 区间差值
    
    def __lt__(self, other):
        # 用于最大堆：值大的优先级高
        return self.val > other.val
    
    def __repr__(self):
        return f"Item(l={self.l}, r={self.r}, val={self.val})"

def max_total_value(nums, k):
    """计算前k个最大子数组差值之和"""
    st = ST(nums)
    n = len(nums)
    
    # 创建优先队列（最大堆）
    pq = []
    
    # 将所有以0为左边界的子数组加入优先队列
    for i in range(n):
        item = Item(0, i, st.query(0, i))
        heapq.heappush(pq, item)
    
    total = 0
    
    # 取前k个最大的差值
    for _ in range(k):
        if not pq:
            break
            
        # 取出当前最大的
        item = heapq.heappop(pq)
        total += item.val
        
        # 如果左边界还可以右移，将新的子数组加入队列
        if item.l + 1 <= item.r:
            new_item = Item(
                item.l + 1, 
                item.r, 
                st.query(item.l + 1, item.r)
            )
            heapq.heappush(pq, new_item)
    
    return total

def main():
    nums = [4, 2, 5, 1]
    k = 3
    result = max_total_value(nums, k)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

// ST 稀疏表，用于快速查询区间最大值和最小值
class ST {
private:
    vector<vector<int>> stMin; // 最小值表
    vector<vector<int>> stMax; // 最大值表

public:
    // 创建新的稀疏表
    ST(const vector<int>& arr) {
        int n = arr.size();
        int k = 32 - __builtin_clz(n); // 计算需要的层数，相当于bits.Len32

        // 初始化第0层
        stMin.resize(n, vector<int>(k));
        stMax.resize(n, vector<int>(k));

        for (int i = 0; i < n; i++) {
            stMin[i][0] = arr[i];
            stMax[i][0] = arr[i];
        }

        // 构建稀疏表
        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                stMin[i][j] = min(stMin[i][j-1], stMin[i + (1 << (j-1))][j-1]);
                stMax[i][j] = max(stMax[i][j-1], stMax[i + (1 << (j-1))][j-1]);
            }
        }
    }

    // 查询区间[l, r]的最大值与最小值之差
    int query(int l, int r) {
        intlen = r - l + 1;
        int k = 31 - __builtin_clz(len); // 相当于LeadingZeros32的逆操作

        // 区间最大值
        int maxVal = max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
        // 区间最小值
        int minVal = min(stMin[l][k], stMin[r - (1 << k) + 1][k]);

        return maxVal - minVal;
    }
};

// Item 优先队列中的元素
struct Item {
    int l;   // 左边界
    int r;   // 右边界
    int val; // 区间差值

    Item(int left, int right, int value) : l(left), r(right), val(value) {}

    // 用于优先队列的比较，值大的优先级高
    bool operator<(const Item& other) const {
        return val < other.val; // 注意：这里使用小于号实现最大堆
    }
};

// maxTotalValue 计算前k个最大子数组差值之和
long long maxTotalValue(const vector<int>& nums, int k) {
    ST st(nums);
    int n = nums.size();

    // 创建优先队列（最大堆）
    priority_queue<Item> pq;

    // 将所有以0为左边界的子数组加入优先队列
    for (int i = 0; i < n; i++) {
        pq.push(Item(0, i, st.query(0, i)));
    }

    long long sum = 0;

    // 取前k个最大的差值
    while (k > 0 && !pq.empty()) {
        // 取出当前最大的
        Item item = pq.top();
        pq.pop();
        sum += item.val;

        // 如果左边界还可以右移，将新的子数组加入队列
        if (item.l + 1 <= item.r) {
            pq.push(Item(item.l + 1, item.r, st.query(item.l + 1, item.r)));
        }

        k--;
    }

    return sum;
}

int main() {
    vector<int> nums = {4, 2, 5, 1};
    int k = 3;
    long long result = maxTotalValue(nums, k);
    cout << result << endl;

    return0;
}