### 题目描述 给你一个整数数组 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 ### 题目解答 #### 思路1 二次循环遍历子数组 通过2次循环对所有子数组进行遍历，在遍历的过程中不断更新min和max，并且将其加入到结果中。 **算法复杂度：** 时间复杂度：2次循环遍历，$$O(n^2)$$ 空间复杂度：没有额外开销，$$O(1)$$ #### 代码实现 ```python def subArrayRanges(self, nums: List[int]) -> int: res = 0 for i in range(len(nums)): min = nums[i] max = nums[i] for j in range(i+1, len(nums)): if nums[j] > max: max = nums[j] if nums[j] < min: min = nums[j] res += max - min return res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复