LeetCode-2104. 子数组范围和【栈 数组 单调栈】
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
-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)
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!