leetcode
leetcode 1851 ~ 1900
子数组范围和

子数组范围和

难度:

标签:

题目描述

代码结果

运行时间: 42 ms, 内存: 16.2 MB


/* 思路:
 * 使用Java Stream来生成子数组的所有范围。
 * 这个方法使用传统for循环来生成子数组范围,再利用Stream API进行后续处理。
 */
import java.util.stream.IntStream;
public class SubarrayRangesStream {
    public static long subArrayRanges(int[] nums) {
        return IntStream.range(0, nums.length)
                .mapToLong(i -> IntStream.range(i, nums.length)
                        .mapToObj(j -> {
                            int min = nums[i], max = nums[i];
                            for (int k = i; k <= j; k++) {
                                min = Math.min(min, nums[k]);
                                max = Math.max(max, nums[k]);
                            }
                            return (long)(max - min);
                        })
                        .mapToLong(Long::longValue)
                        .sum())
                .sum();
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(subArrayRanges(nums)); // 输出: 4
    }
}

解释

方法:

本题解采用了单调栈的技术来计算每个元素作为最大值和最小值对所有可能子数组范围的贡献。首先,使用一个单调递增栈来计算每个元素作为最大值的贡献。遍历数组时,对于每个元素,如果它大于栈顶元素,那么栈顶元素不能再作为最大值,我们计算并累加该元素为最大值时的贡献。然后,使用一个单调递减栈来计算每个元素作为最小值的贡献,过程类似但贡献是被减去的,因为我们最终需要的是范围,即最大值减去最小值的结果。通过这种方式,我们只需要遍历数组两次,就能求出所有子数组的范围和。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择使用单调栈来解决这个问题,而不是其他数据结构如分段树或二分搜索树?
单调栈被选择是因为它能以线性时间复杂度处理和解决子数组最值问题,特别适合于解决本题中需要快速找到每个元素作为子数组最大值和最小值的问题。单调栈可以通过一次遍历即可实现对每个元素左右边界的确定,而分段树或二分搜索树虽然在区间查询和更新上表现优越,但在本题中处理单点更新和区间最值查询的复杂度和需要的编码量较大,不如单调栈直观和高效。
🦆
单调递增栈和单调递减栈在这里是如何具体帮助我们找到每个元素作为最大值和最小值的所有可能子数组的?
单调递增栈帮助我们确定一个元素左侧和右侧第一个比它大的元素的位置,从而确定该元素作为最大值时的所有可能子数组的范围。类似地,单调递减栈帮助我们确定一个元素左侧和右侧第一个比它小的元素的位置,从而确定该元素作为最小值时的所有可能子数组的范围。这样,对于每个元素,我们可以快速计算出其作为最大值或最小值时的贡献,通过单调栈我们可以在一次遍历中完成这些计算,极大地提高了效率。
🦆
在代码中,为什么在数组 `nums` 的末尾添加 `float('inf')` 和 `float('-inf')`,这样做有什么作用?
在数组 `nums` 的末尾添加 `float('inf')` 和 `float('-inf')` 是为了确保所有元素都能从栈中弹出。这样做的目的是强制触发栈中所有元素的弹出过程,无论是单调递增栈还是单调递减栈。这保证了每个元素都能完全计算其作为最大值或最小值的贡献,因为添加的无穷大或无穷小元素会比任何实际元素大或小,从而导致栈中元素的连续弹出,完成所有计算。

相关问题