当前位置：首页 > news >正文

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

news 2026/6/29 8:50:05

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;
}
}
```