文章目录
1. 题目
给你一个整数数组 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^9 <= nums[i] <= 10^9
2. 解题
- 单调栈,获取每个数字作为最大或者最小的左右极限位置
- 单独考虑每个数字可以作为最大值或者最小值的次数,到左右极限位置处的个数相乘种组合
class Solution: def subArrayRanges(self, nums: List[int]) -> int: def getRange(nums, neg): nums_ = copy.deepcopy(nums) if neg: for i in range(len(nums)): nums_[i] = -nums_[i] # 找最小值的左右区间,取个负数,逻辑跟正数一样 L, R = list(range(len(nums))), list(range(len(nums))) q = [] for i in range(len(nums)): while len(q) and nums_[q[-1]] < nums_[i]: q.pop() L[i] = q[-1]+1 if len(q) else 0 q.append(i) q = [] for i in reversed(range(len(nums))): while len(q) and nums_[q[-1]] <= nums_[i]: q.pop() # 注意上下只能有一个 = 号 R[i] = q[-1]-1 if len(q) else (len(nums)-1) q.append(i) return L, R L1, R1 = getRange(nums, neg=False) L2, R2 = getRange(nums, neg=True) ans = 0 for i in range(len(nums)): # print(L1[i], R1[i], L2[i], R2[i]) ans += (R1[i]-i+1)*(i-L1[i]+1)*nums[i]-(R2[i]-i+1)*(i-L2[i]+1)*nums[i] return ans
140 ms 15.2 MB Python3