LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.09
• 题目：3691. 最大化子数组总值 II
• 难度：困难
• 标签：单调栈、优先队列、笛卡尔树、贪心

1. 题目理解

问题描述： 给定数组 nums 和整数 k，你需要选择 恰好 k 个非空子数组。 每个子数组的价值 = 子数组内最大值 - 最小值。 求选择 k 个子数组能得到的最大总价值。

示例：

输入：nums = [1,3,2], k = 2 输出：4 解释：选两次 [1,3]，价值都是 2，总和 4。

2. 解题思路

核心观察

1. 子数组价值 = max - min，要总和最大，必须优先选价值最大的子数组。
2. 暴力枚举所有子数组会超时，必须用贪心 + 优先队列高效取前 k 大价值。
3. 优化版核心：
   • 用单调栈预处理每个元素作为 min 的有效区间。
   • 用排序 + 优先队列批量计算相同最大差值的子数组数量。
   • 直接批量累加，避免逐个取出，时间复杂度从 $O(n^2\log n)$ 优化到 $O(n\log n)$。

算法步骤

1. 单调栈求每个元素作为最小值的左右边界。
2. 排序得到元素大小关系。
3. 优先队列维护当前最大价值区间。
4. 每次取出最大价值，批量计算能取多少个，直接累加。
5. 分裂区间继续入队，直到取满 k 个。

3. 代码实现

package lc3600_lc3699.lc3691;

import java.util.PriorityQueue;

class Solution {
    public int log2(int x) {
        return 31 - Integer.numberOfLeadingZeros(x);
    }

    int[][] stMax;
    int[][] stMin;
    int[] logTable;

    public void build(int[] nums) {
        int n = nums.length;
        if (n == 0) return;

        int K = log2(n) + 1;
        stMax = new int[K][n];
        stMin = new int[K][n];
        logTable = new int[n + 1];


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


        for (int j = 1; j < K; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                int mid = i + (1 << (j - 1));
                stMax[j][i] = Math.max(stMax[j - 1][i], stMax[j - 1][mid]);
                stMin[j][i] = Math.min(stMin[j - 1][i], stMin[j - 1][mid]);
            }
        }


        logTable[1] = 0;
        for (int len = 2; len <= n; len++) {
            logTable[len] = log2(len);
        }
    }


    public int queryMax(int l, int r) {
        int len = r - l + 1;
        int k = logTable[len];
        return Math.max(stMax[k][l], stMax[k][r - (1 << k) + 1]);
    }


    public int queryMin(int l, int r) {
        int len = r - l + 1;
        int k = logTable[len];
        return Math.min(stMin[k][l], stMin[k][r - (1 << k) + 1]);
    }


    public int value(int l, int r) {
        return queryMax(l, r) - queryMin(l, r);
    }

    public long maxTotalValue(int[] nums, int k) {
        build(nums);
        long res = 0;
        int n = nums.length;
        if (n == 0) return 0;

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        for (int i = 0; i < n; i++) {
            int l = i;
            int r = n - 1;
            int val = value(l, r);
            maxHeap.add(new int[]{val, l, r});
        }


        while (k > 0 && !maxHeap.isEmpty()) {
            int[] cur = maxHeap.poll();
            int val = cur[0];
            int l = cur[1];
            int r = cur[2];
            res += val;

            if (r > l) {
                int newR = r - 1;
                int newVal = value(l, newR);
                maxHeap.add(new int[]{newVal, l, newR});
            }
            k--;
        }

        return res;
    }
}

4. 代码优化说明

import java.util.*;

class Solution {
    // 优先队列节点：存储最小/最大排名、当前差值
    private static class Node implements Comparable<Node> {
        int minRank, maxRank, diff;
        public Node(int minRank, int maxRank, int diff) {
            this.minRank = minRank;
            this.maxRank = maxRank;
            this.diff = diff;
        }
        @Override
        public int compareTo(Node o) {
            return o.diff - diff;
        }
    }

    public long maxTotalValue(int[] nums, int k) {
        int n = nums.length;
        int[] lefts = new int[n];   // 每个元素作为最小值的左边界
        int[] rights = new int[n];  // 每个元素作为最小值的右边界
        int[] stack = new int[n];
        int top = 0;
        lefts[0] = -1;
        
        // 单调栈预处理每个最小值的作用区间
        for(int i = 1, j = 0; i < n; i++) {
            int num = nums[i];
            for(; num < nums[j];) {
                rights[j] = i;
                if(--top < 0) {
                    j = -1;
                    break;
                }
                j = stack[top];
            }
            lefts[i] = j;
            stack[++top] = j = i;
        }
        do {
            rights[stack[top]] = n;
        } while (--top >= 0);

        // 按值排序，得到元素大小排名
        long[] numIndices = new long[n];
        for(int i = 0; i < n; i++) {
            numIndices[i] = ((long)nums[i] << 32) | i;
        }
        Arrays.sort(numIndices);
        int[] indices = new int[n];
        for(int i = 0; i < n; i++) {
            indices[i] = (int)(numIndices[i] & Integer.MAX_VALUE);
        }

        // 贪心取最大价值区间，批量计算数量
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(0, n - 1, nums[indices[n - 1]] - nums[indices[0]]));
        long sum = 0;
        for(Node node; (node = queue.poll()) != null; ) {
            int minRank = node.minRank;
            int maxRank = node.maxRank;
            int minIndex = indices[minRank];
            int maxIndex = indices[maxRank];
            int count;
            int left = lefts[minIndex];
            int right = rights[minIndex];
            
            // 计算当前差值可选取的子数组数量
            if(maxIndex < minIndex) {
                count = (maxIndex > left) ? (right - minIndex) * (maxIndex - left) : 0;
                lefts[minIndex] = maxIndex;
            } else {
                count = (maxIndex < right) ? (minIndex - left) * (right - maxIndex) : 0;
                rights[minIndex] = maxIndex;
            }
            
            // 满足k个直接返回，否则累加全部并继续
            if(k <= count) {
                sum += (long)node.diff * k;
                return sum;
            } else {
                k -= count;
                sum += (long)node.diff * count;
            }
            
            // 分裂区间继续入队
            if(minRank == 0 && maxRank > 1) {
                queue.add(new Node(minRank, maxRank - 1, nums[indices[maxRank - 1]] - nums[minIndex]));
            }
            if(minRank + 1 < maxRank) {
                queue.add(new Node(minRank + 1, maxRank, nums[maxIndex] - nums[indices[minRank + 1]]));
            }
        }
        return sum;
    }
}

5. 复杂度分析

• 原版 ST 表 + 堆版
  • 时间复杂度：$O(n^2\log n)$，适合小规模数据。
  • 空间复杂度：$O(n\log n)$，ST 表空间。
• 优化版 单调栈 + 批量贪心
  • 时间复杂度：$O(n\log n)$，排序 + 堆操作均为对数级别。
  • 空间复杂度：$O(n)$，线性额外空间。
  • 优势：批量计算子数组数量，避免逐个取出，适合大数据范围（k 极大）。

6. 总结

• 核心：最大价值子数组 = 全局最大 - 全局最小，优先选取价值最大的子数组。
• 优化亮点：
  1. 用单调栈快速确定每个最小值的有效区间。
  2. 用批量计数代替逐个取堆顶，效率提升巨大。
  3. 减少分支判断，代码逻辑更紧凑高效。
• 关键：这道题不是模拟题，而是贪心 + 数据结构的组合难题。