LeetCode 3430. 最多 K 个元素的子数组的最值之和

题目分析

给定一个整数数组 nums 和一个整数 k，需要找出所有长度不超过 k 的连续子数组中，最大值和最小值之和的总和。

解题思路

核心思想

对于每个元素，计算它作为最大值和最小值时，对答案的贡献次数。

关键步骤

1. 计算作为最大值的贡献
   · 找到每个元素左边第一个大于它的元素位置
   · 找到每个元素右边第一个大于等于它的元素位置（处理重复元素）
   · 计算以该元素为最大值的子数组数量，且长度 ≤ k
2. 计算作为最小值的贡献
   · 找到每个元素左边第一个小于它的元素位置
   · 找到每个元素右边第一个小于等于它的元素位置（处理重复元素）
   · 计算以该元素为最小值的子数组数量，且长度 ≤ k
3. 答案 = 最大值贡献总和 + 最小值贡献总和

时间复杂度

· O(n)，使用单调栈

Java实现

```java
class Solution {
    public long minMaxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long ans = 0;
        
        // 计算作为最大值的贡献
        int[] leftGreater = new int[n];
        int[] rightGreaterEqual = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 左边第一个大于当前元素的索引
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            leftGreater[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        // 右边第一个大于等于当前元素的索引
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                stack.pop();
            }
            rightGreaterEqual[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        // 计算最大值的贡献
        for (int i = 0; i < n; i++) {
            int left = i - leftGreater[i];
            int right = rightGreaterEqual[i] - i;
            ans += (long) nums[i] * countSubarrays(left, right, k);
        }
        
        // 计算作为最小值的贡献
        int[] leftSmaller = new int[n];
        int[] rightSmallerEqual = new int[n];
        stack.clear();
        
        // 左边第一个小于当前元素的索引
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        // 右边第一个小于等于当前元素的索引
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                stack.pop();
            }
            rightSmallerEqual[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        // 计算最小值的贡献
        for (int i = 0; i < n; i++) {
            int left = i - leftSmaller[i];
            int right = rightSmallerEqual[i] - i;
            ans += (long) nums[i] * countSubarrays(left, right, k);
        }
        
        return ans;
    }
    
    // 计算在 left × right 的网格中，包含当前元素且长度 ≤ k 的子数组数量
    private long countSubarrays(int left, int right, int k) {
        long total = 0;
        // 枚举左边取 x 个，右边取 y 个，满足 x + y + 1 ≤ k
        // x ∈ [0, left-1], y ∈ [0, right-1]
        int maxX = Math.min(left - 1, k - 1);
        int maxY = Math.min(right - 1, k - 1);
        
        // 使用数学公式计算
        for (int x = 0; x <= maxX; x++) {
            int remain = k - 1 - x;
            int yLimit = Math.min(maxY, remain);
            if (yLimit >= 0) {
                total += (yLimit + 1);
            }
        }
        return total;
    }
}
```

优化版本（使用前缀和优化 countSubarrays）AC

```java
class Solution {
    public long minMaxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long ans = 0;
        
        // 计算最大值的贡献
        int[] leftGreater = new int[n];
        int[] rightGreaterEqual = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            leftGreater[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                stack.pop();
            }
            rightGreaterEqual[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        for (int i = 0; i < n; i++) {
            int left = i - leftGreater[i];
            int right = rightGreaterEqual[i] - i;
            ans += (long) nums[i] * countSubarraysOptimized(left, right, k);
        }
        
        // 计算最小值的贡献
        int[] leftSmaller = new int[n];
        int[] rightSmallerEqual = new int[n];
        stack.clear();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                stack.pop();
            }
            rightSmallerEqual[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        for (int i = 0; i < n; i++) {
            int left = i - leftSmaller[i];
            int right = rightSmallerEqual[i] - i;
            ans += (long) nums[i] * countSubarraysOptimized(left, right, k);
        }
        
        return ans;
    }
    
    // 优化版本：使用数学公式 O(1) 计算
    private long countSubarraysOptimized(int left, int right, int k) {
        long l = Math.min(left, k);
        long r = Math.min(right, k);
        
        if (l == 0 || r == 0) return 0;
        
        // 计算所有可能的 (x, y) 对数，其中 x ∈ [0, l-1], y ∈ [0, r-1], x + y ≤ k-1
        long total = 0;
        long maxSum = k - 1;
        
        if (l + r - 2 <= maxSum) {
            // 所有组合都满足
            return l * r;
        }
        
        // 分情况计算
        // 情况1: x 较小，y 可以取全部
        for (long x = 0; x < l && x <= maxSum; x++) {
            long yMax = Math.min(r - 1, maxSum - x);
            if (yMax >= 0) {
                total += yMax + 1;
            }
        }
        
        return total;
    }
}
```

关键点说明

1. 单调栈的使用：用单调栈找到每个元素作为最值的边界
2. 处理重复元素：使用 > 和 >= 的不同组合来避免重复计算
3. 长度限制 k：在计算子数组数量时，需要限制左右扩展的总长度不超过 k
4. 数据类型：使用 long 避免整数溢出

这个解法的时间复杂度为 O(n)，空间复杂度为 O(n)。