LeetCode-2104. 子数组范围和【栈 数组 单调栈】

题目描述

给你一个整数数组 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
-10⁹ <= nums[i] <= 10⁹

解题思路一暴力解法。用两个指针代表连续子数组的边界同时更新最大最小值并且得到答案。

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)

        for i in range(n):
            minVal, maxVal = inf, -inf
            for j in range(i,n):
                maxVal = max(nums[j], maxVal)
                minVal = min(nums[j], minVal)
                ans += maxVal - minVal

        return ans

时间复杂度O(n²) 两层for
空间复杂度O(1)

解题思路二单调栈维护四个数组。minLeft, maxLeftminRight, maxRight分别记录左边第一个小的左边第一个大的右边第一个小的和右边第一个大的。最终的答案是sumMax - sumMin。其中sumMax 和 sumMin 定义如下。

for i, num in enumerate(nums):
  sumMax += (maxRight[i] - i) * (i - maxLeft[i]) * num
  sumMin += (minRight[i] - i) * (i - minLeft[i]) * num

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)
        minLeft, maxLeft = [0] * n, [0] * n
        minStack, maxStack = [], []
        for i, num in enumerate(nums):
            while minStack and nums[minStack[-1]] > num:
                minStack.pop()
            minLeft[i] = minStack[-1] if minStack else -1
            minStack.append(i)

            # 如果 nums[maxStack[-1]] == num, 那么根据定义
            # nums[maxStack[-1]] 逻辑上小于 num因为 maxStack[-1] < i
            while maxStack and nums[maxStack[-1]] <= num:
                maxStack.pop()
            maxLeft[i] = maxStack[-1] if maxStack else -1
            maxStack.append(i)

        minRight, maxRight = [0] * n, [0] * n
        minStack, maxStack = [], []
        for i in range(n - 1, -1, -1):
            num = nums[i]
            # 如果 nums[minStack[-1]] == num, 那么根据定义
            # nums[minStack[-1]] 逻辑上大于 num因为 minStack[-1] > i
            while minStack and nums[minStack[-1]] >= num:
                minStack.pop()
            minRight[i] = minStack[-1] if minStack else n
            minStack.append(i)

            while maxStack and nums[maxStack[-1]] < num:
                maxStack.pop()
            maxRight[i] = maxStack[-1] if maxStack else n
            maxStack.append(i)

        sumMax, sumMin = 0, 0
        for i, num in enumerate(nums):# 记录当前元素i是多少个子数组的最小值和最大值
            sumMax += (maxRight[i] - i) * (i - maxLeft[i]) * num
            sumMin += (minRight[i] - i) * (i - minLeft[i]) * num
        return sumMax - sumMin

时间复杂度O(n) 维护四个数组
空间复杂度O(n) 数组
比较难以想到的就是
根据范围和的定义可以推出范围和 sum 等于所有子数组的最大值之和 sumMax 减去所有子数组的最小值之和 sumMin。

解题思路三0

时间复杂度O(n)
空间复杂度O(n)