子数组范围和

标签: 栈 数组 单调栈

难度: Medium

给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。

返回 nums 中 所有 子数组范围的 和 。

子数组是数组中一个连续 非空 的元素序列。

示例 1：

输入：nums = [1,2,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0 
[2]，范围 = 2 - 2 = 0
[3]，范围 = 3 - 3 = 0
[1,2]，范围 = 2 - 1 = 1
[2,3]，范围 = 3 - 2 = 1
[1,2,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4

示例 2：

输入：nums = [1,3,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[3]，范围 = 3 - 3 = 0
[3]，范围 = 3 - 3 = 0
[1,3]，范围 = 3 - 1 = 2
[3,3]，范围 = 3 - 3 = 0
[1,3,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4

示例 3：

输入：nums = [4,-2,-3,4,1]
输出：59
解释：nums 中所有子数组范围的和是 59

提示：

  • 1 <= nums.length <= 1000
  • -109 <= nums[i] <= 109

进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？

Submission

运行时间: 42 ms

内存: 16.2 MB

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans, st = 0, []
        for i,num in enumerate(nums+[float('inf')]):
            while st and num > nums[st[-1]]:
                index = st.pop(-1)
                # print(nums[index] * (index - i) * (index- st[-1] if st else -1))
                ans += (nums[index] * (i-index) * (index- (st[-1] if st else -1)))
            st.append(i)
        st = []
        for i,num in enumerate(nums+[float('-inf')]):
            while st and num < nums[st[-1]]:
                index = st.pop(-1)
                # print(nums[index] * (index - i) * (index- st[-1] if st else -1))
                ans -= (nums[index] * (i-index) * (index- (st[-1] if st else -1)))
            st.append(i)
        return ans
        # print(ans)
        # res = 0
        # for i in range(len(nums)):
        #     for j in range(i+1,len(nums)):
        #         if j == i+1:
        #             min_v = min(nums[i],nums[j])
        #             max_v = max(nums[i],nums[j])
        #         else:
        #             if nums[j] > max_v:
        #                 max_v = nums[j]
        #             if nums[j] < min_v:
        #                 min_v = nums[j]
        #         res += (max_v-min_v)
        # return res

Explain

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

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans, st = 0, []
        # 使用单调递增栈计算每个元素作为最大值的贡献
        for i,num in enumerate(nums+[float('inf')]):
            while st and num > nums[st[-1]]:
                index = st.pop(-1)
                # 计算nums[index]作为最大值的贡献
                ans += (nums[index] * (i-index) * (index- (st[-1] if st else -1)))
            st.append(i)
        st = []
        # 使用单调递减栈计算每个元素作为最小值的贡献
        for i,num in enumerate(nums+[float('-inf')]):
            while st and num < nums[st[-1]]:
                index = st.pop(-1)
                # 计算nums[index]作为最小值的贡献
                ans -= (nums[index] * (i-index) * (index- (st[-1] if st else -1)))
            st.append(i)
        return ans

Explore

单调栈被选择是因为它能以线性时间复杂度处理和解决子数组最值问题，特别适合于解决本题中需要快速找到每个元素作为子数组最大值和最小值的问题。单调栈可以通过一次遍历即可实现对每个元素左右边界的确定，而分段树或二分搜索树虽然在区间查询和更新上表现优越，但在本题中处理单点更新和区间最值查询的复杂度和需要的编码量较大，不如单调栈直观和高效。

单调递增栈帮助我们确定一个元素左侧和右侧第一个比它大的元素的位置，从而确定该元素作为最大值时的所有可能子数组的范围。类似地，单调递减栈帮助我们确定一个元素左侧和右侧第一个比它小的元素的位置，从而确定该元素作为最小值时的所有可能子数组的范围。这样，对于每个元素，我们可以快速计算出其作为最大值或最小值时的贡献，通过单调栈我们可以在一次遍历中完成这些计算，极大地提高了效率。

在数组 `nums` 的末尾添加 `float('inf')` 和 `float('-inf')` 是为了确保所有元素都能从栈中弹出。这样做的目的是强制触发栈中所有元素的弹出过程，无论是单调递增栈还是单调递减栈。这保证了每个元素都能完全计算其作为最大值或最小值的贡献，因为添加的无穷大或无穷小元素会比任何实际元素大或小，从而导致栈中元素的连续弹出，完成所有计算。