LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.09
• 题目：3689. 最大子数组总值 I
• 难度：中等
• 标签：数组、数学、贪心

1. 题目理解

问题描述： 给定长度为 n 的整数数组 nums 和整数 k，必须从 nums 中选择恰好 k 个非空子数组（可重复选择）。 子数组的值定义为：max(nums[l..r]) - min(nums[l..r])。 求所有被选子数组的值之和的最大值。

示例：

输入：nums = [1,3,2], k = 2 输出：4 解释：两次都选择 [1,3] 或 [1,3,2]，值均为 3-1=2，总和为 2+2=4。

2. 解题思路

核心观察

• 子数组的最大值为整个数组的最大值 max，最小值为整个数组的最小值 min，它们的差 max-min 是所有子数组中能达到的最大值。
• 题目允许重复选择同一个子数组，因此每次都选择这个差值最大的子数组，连续选 k 次，就能得到最大总值。
• 因此答案为 (max - min) * k。

算法步骤

1. 遍历数组，找到全局最大值 max 和全局最小值 min；
2. 计算最大差值 max - min；
3. 乘以 k 得到最终结果。

3. 代码实现

class Solution {
    public long maxTotalValue(int[] nums, int k) {
        long res = 0L;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(min,nums[i]);
            max = Math.max(max,nums[i]);
        }
        long i = (max - min);
        res = i *k;
        return res;
    }
}

4. 代码优化说明

class Solution {
    public long maxTotalValue(int[] nums, int k) {
        // 初始化最小/最大值为数组第一个元素
        int min = nums[0], max = nums[0];
        // 一次遍历同时更新最小、最大值
        for (int num : nums) {
            min = num < min ? num : min;
            max = num > max ? num : max;
        }
        // 直接计算并返回结果，减少中间变量
        return (long) (max - min) * k;
    }
}

5. 复杂度分析

• 原版代码 时间复杂度：$O(n)$，一次遍历找最大最小值 空间复杂度：$O(1)$，仅使用常数变量
• 优化代码 时间复杂度：$O(n)$，同样一次遍历 空间复杂度：$O(1)$，无额外空间开销 优化点：精简变量、减少分支、去掉冗余计算，代码更简洁高效

6. 总结

• 核心：这是一道数学规律题，最优解就是全局最大差值 × k；
• 关键：题目允许重复选择子数组，因此只需要选择差值最大的子数组 k 次；
• 优化点：减少了不必要的中间变量，用三元运算符替代 Math.min/max，代码更紧凑。