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

2023-12-14 16:46:47

题目描述:

给你一个整数数组 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

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

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(n2) 两层for
空间复杂度:O(1)

解题思路二:单调栈,维护四个数组。minLeft, maxLeft,minRight, 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)

文章来源:https://blog.csdn.net/qq_45934285/article/details/134996989
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。