LeetCode 3430. 最多 K 个元素的子数组的最值之和题目分析给定一个整数数组 nums 和一个整数 k需要找出所有长度不超过 k 的连续子数组中最大值和最小值之和的总和。解题思路核心思想对于每个元素计算它作为最大值和最小值时对答案的贡献次数。关键步骤1. 计算作为最大值的贡献· 找到每个元素左边第一个大于它的元素位置· 找到每个元素右边第一个大于等于它的元素位置处理重复元素· 计算以该元素为最大值的子数组数量且长度 ≤ k2. 计算作为最小值的贡献· 找到每个元素左边第一个小于它的元素位置· 找到每个元素右边第一个小于等于它的元素位置处理重复元素· 计算以该元素为最小值的子数组数量且长度 ≤ k3. 答案 最大值贡献总和 最小值贡献总和时间复杂度· O(n)使用单调栈Java实现javaclass 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];DequeInteger 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;}}优化版本使用前缀和优化 countSubarraysACjavaclass 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];DequeInteger 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-1long 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在计算子数组数量时需要限制左右扩展的总长度不超过 k4. 数据类型使用 long 避免整数溢出这个解法的时间复杂度为 O(n)空间复杂度为 O(n)。
