<div>
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.
Return the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
<pre>Input: nums = [1,2,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [2], range = 2 - 2 = 0 [3], range = 3 - 3 = 0 [1,2], range = 2 - 1 = 1 [2,3], range = 3 - 2 = 1 [1,2,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.</pre>
Example 2:
<pre>Input: nums = [1,3,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [3], range = 3 - 3 = 0 [3], range = 3 - 3 = 0 [1,3], range = 3 - 1 = 2 [3,3], range = 3 - 3 = 0 [1,3,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4. </pre>
Example 3:
<pre>Input: nums = [4,-2,-3,4,1] Output: 59 Explanation: The sum of all subarray ranges of nums is 59. </pre>
Constraints:
1 <= nums.length <= 1000-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
</div>
题目大意：
求所有子数组的最大值最小值之差的和
Stack算法思路：
参考Leetcode 907，分别求子数组最小值的相反数，子数组的最大值，这两个值的和即为所求
注意事项：
- 最小值用递增栈，最大值用递减栈
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21def subArrayRanges(self, nums: List[int]) -> int:
arr = list(nums)
arr.insert(0, -sys.maxsize)
arr.append(-sys.maxsize)
stack, res, = [], 0
for i in range(len(arr)):
while stack and arr[i] < arr[stack[-1]]:
prev_idx = stack.pop()
res -= arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
stack.append(i)
arr = list(nums)
arr.insert(0, sys.maxsize)
arr.append(sys.maxsize)
for i in range(len(arr)):
while stack and arr[i] > arr[stack[-1]]:
prev_idx = stack.pop()
res += arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
stack.append(i)
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
累计和算法II解题思路：
比暴力法稍优，两重循环覆盖所有子数组[i, j]，每轮循环得到最大最小值，然后O(1)内求该区间内所有最大最小值差值和。
Python代码：
1
2
3
4
5
6
7
8
9def subArrayRanges(self, nums: List[int]) -> int:
sum = 0
for i in range(len(nums) - 1):
min_value, max_value = nums[i], nums[i]
for j in range(i + 1, len(nums)):
min_value = min(min_value, nums[j])
max_value = max(max_value, nums[j])
sum += max_value - min_value
return sum
算法分析：
时间复杂度为O(n^2)，空间复杂度O(1)
