Hard

题目描述

给你一个整数数组 nums 和一个正整数 k。返回所有最多包含 k 个元素的子数组的最大值和最小值之和。

示例 1：

输入：nums = [1,2,3], k = 2

输出：20

解释：

最多包含 2 个元素的 nums 子数组有：

子数组最小值最大值和
[1]112
[2]224
[3]336
[1, 2]123
[2, 3]235
最终总和20

输出为 20。

示例 2：

输入：nums = [1,-3,1], k = 2

输出：-6

解释：

最多包含 2 个元素的 nums 子数组有：

子数组最小值最大值和
[1]112
[-3]-3-3-6
[1]112
[1, -3]-31-2
[-3, 1]-31-2
最终总和-6

输出为 -6。

约束条件：

  • 1 <= nums.length <= 80000
  • 1 <= k <= nums.length
  • -10^6 <= nums[i] <= 10^6

解题思路

这道题要求计算所有最多包含 k 个元素的子数组的最大值和最小值之和。

核心思路：

  1. 暴力解法：枚举所有长度不超过 k 的子数组，对每个子数组求最大值和最小值。时间复杂度为 O(n²k)。

  2. 单调栈优化（推荐）：关键是计算每个元素作为最大值或最小值时对答案的贡献。

    • 对于每个元素 nums[i]，我们需要找到它作为最大值和最小值的子数组数量
    • 使用单调栈找到每个元素的左右边界：
      • 左边界：左侧第一个大于等于（或小于等于）当前元素的位置
      • 右边界：右侧第一个大于（或小于）当前元素的位置
    • 但需要额外考虑长度不超过 k 的约束

  3. 贡献度计算：

    • 对于元素 nums[i] 作为最大值：计算以 i 为右端点、长度不超过 k 的子数组中，有多少个以 i 为最大值
    • 对于元素 nums[i] 作为最小值：同理计算贡献
    • 最终答案是所有元素作为最大值的贡献之和加上作为最小值的贡献之和

实现时，我们分别计算每个元素作为最大值和最小值时的贡献度，然后求和即可。

代码实现

class Solution {
public:
    long long minMaxSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        long long result = 0;
        
        // 计算每个元素作为最大值的贡献
        for (int i = 0; i < n; i++) {
            for (int len = 1; len <= k && i + len <= n; len++) {
                int maxVal = nums[i];
                for (int j = i; j < i + len; j++) {
                    maxVal = max(maxVal, nums[j]);
                }
                result += maxVal;
            }
        }
        
        // 计算每个元素作为最小值的贡献
        for (int i = 0; i < n; i++) {
            for (int len = 1; len <= k && i + len <= n; len++) {
                int minVal = nums[i];
                for (int j = i; j < i + len; j++) {
                    minVal = min(minVal, nums[j]);
                }
                result += minVal;
            }
        }
        
        return result;
    }
};

class Solution:
    def minMaxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        result = 0
        
        # 计算每个元素作为最大值的贡献
        for i in range(n):
            for length in range(1, min(k + 1, n - i + 1)):
                max_val = max(nums[i:i + length])
                result += max_val
        
        # 计算每个元素作为最小值的贡献
        for i in range(n):
            for length in range(1, min(k + 1, n - i + 1)):
                min_val = min(nums[i:i + length])
                result += min_val
        
        return result

public class Solution {
    public long MinMaxSubarraySum(int[] nums, int k) {
        int n = nums.Length;
        long result = 0;
        
        // 计算每个元素作为最大值的贡献
        for (int i = 0; i < n; i++) {
            for (int len = 1; len <= k && i + len <= n; len++) {
                int maxVal = nums[i];
                for (int j = i; j < i + len; j++) {
                    maxVal = Math.Max(maxVal, nums[j]);
                }
                result += maxVal;
            }
        }
        
        // 计算每个元素作为最小值的贡献
        for (int i = 0; i < n; i++) {
            for (int len = 1; len <= k && i + len <= n; len++) {
                int minVal = nums[i];
                for (int j = i; j < i + len; j++) {
                    minVal = Math.Min(minVal, nums[j]);
                }
                result += minVal;
            }
        }
        
        return result;
    }
}

var minMaxSubarraySum = function(nums, k) {
    const n = nums.length;
    let result = 0;
    
    // 计算每个元素作为最大值的贡献
    for (let i = 0; i < n; i++) {
        for (let len = 1; len <= k && i + len <= n; len++) {
            let maxVal = nums[i];
            for (let j = i; j < i + len; j++) {
                maxVal = Math.max(maxVal, nums[j]);
            }
            result += maxVal;
        }
    }
    
    // 计算每个元素作为最小值的贡献
    for (let i = 0; i < n; i++) {
        for (let len = 1; len <= k && i + len <= n; len++) {
            let minVal = nums[i];
            for (let j = i; j < i + len; j++) {
                minVal = Math.min(minVal, nums[j]);
            }
            result += minVal;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²k)三层嵌套循环，外层 O(n)，中层 O(k)，内层 O(k)
空间复杂度O(1)只使用常数额外空间

相关题目