class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
}
};
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
进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？
原站题解
python3 解法, 执行用时: 76 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-29 11:58:51
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):
sumMax += (maxRight[i] - i) * (i - maxLeft[i]) * num
sumMin += (minRight[i] - i) * (i - minLeft[i]) * num
return sumMax - sumMin
javascript 解法, 执行用时: 80 ms, 内存消耗: 46.8 MB, 提交时间: 2022-11-29 11:58:30
/**
* @param {number[]} nums
* @return {number}
*/
var subArrayRanges = function(nums) {
const n = nums.length;
const minLeft = new Array(n).fill(0);
const minRight = new Array(n).fill(0);
const maxLeft = new Array(n).fill(0);
const maxRight = new Array(n).fill(0);
let minStack = [];
let maxStack = [];
for (let i = 0; i < n; i++) {
while (minStack.length && nums[minStack[minStack.length - 1]] > nums[i]) {
minStack.pop();
}
minLeft[i] = minStack.length === 0 ? -1 : minStack[minStack.length - 1];
minStack.push(i);
// 如果 nums[maxStack[maxStack.length - 1]] == nums[i], 那么根据定义，
// nums[maxStack[maxStack.length - 1]] 逻辑上小于 nums[i]，因为 maxStack[maxStack.length - 1] < i
while (maxStack.length && nums[maxStack[maxStack.length - 1]] <= nums[i]) {
maxStack.pop();
}
maxLeft[i] = maxStack.length === 0 ? -1 : maxStack[maxStack.length - 1];
maxStack.push(i);
}
minStack = [];
maxStack = [];
for (let i = n - 1; i >= 0; i--) {
// 如果 nums[minStack[minStack.length - 1]] == nums[i], 那么根据定义，
// nums[minStack[minStack.length - 1]] 逻辑上大于 nums[i]，因为 minStack[minStack.length - 1] > i
while (minStack.length && nums[minStack[minStack.length - 1]] >= nums[i]) {
minStack.pop();
}
minRight[i] = minStack.length === 0 ? n : minStack[minStack.length - 1];
minStack.push(i);
while (maxStack.length && nums[maxStack[maxStack.length - 1]] < nums[i]) {
maxStack.pop();
}
maxRight[i] = maxStack.length === 0 ? n : maxStack[maxStack.length - 1];
maxStack.push(i);
}
let sumMax = 0, sumMin = 0;
for (let i = 0; i < n; i++) {
sumMax += (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
sumMin += (minRight[i] - i) * (i - minLeft[i]) * nums[i];
}
return sumMax - sumMin;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 5.2 MB, 提交时间: 2022-11-29 11:57:55
func subArrayRanges(nums []int) int64 {
n := len(nums)
minLeft := make([]int, n)
maxLeft := make([]int, n)
var minStk, maxStk []int
for i, num := range nums {
for len(minStk) > 0 && nums[minStk[len(minStk)-1]] > num {
minStk = minStk[:len(minStk)-1]
}
if len(minStk) > 0 {
minLeft[i] = minStk[len(minStk)-1]
} else {
minLeft[i] = -1
}
minStk = append(minStk, i)
// 如果 nums[maxStk[len(maxStk)-1]] == num, 那么根据定义，
// nums[maxStk[len(maxStk)-1]] 逻辑上小于 num，因为 maxStk[len(maxStk)-1] < i
for len(maxStk) > 0 && nums[maxStk[len(maxStk)-1]] <= num {
maxStk = maxStk[:len(maxStk)-1]
}
if len(maxStk) > 0 {
maxLeft[i] = maxStk[len(maxStk)-1]
} else {
maxLeft[i] = -1
}
maxStk = append(maxStk, i)
}
minRight := make([]int, n)
maxRight := make([]int, n)
minStk = minStk[:0]
maxStk = maxStk[:0]
for i := n - 1; i >= 0; i-- {
num := nums[i]
// 如果 nums[minStk[len(minStk)-1]] == num, 那么根据定义，
// nums[minStk[len(minStk)-1]] 逻辑上大于 num，因为 minStk[len(minStk)-1] > i
for len(minStk) > 0 && nums[minStk[len(minStk)-1]] >= num {
minStk = minStk[:len(minStk)-1]
}
if len(minStk) > 0 {
minRight[i] = minStk[len(minStk)-1]
} else {
minRight[i] = n
}
minStk = append(minStk, i)
for len(maxStk) > 0 && nums[maxStk[len(maxStk)-1]] < num {
maxStk = maxStk[:len(maxStk)-1]
}
if len(maxStk) > 0 {
maxRight[i] = maxStk[len(maxStk)-1]
} else {
maxRight[i] = n
}
maxStk = append(maxStk, i)
}
var sumMax, sumMin int64
for i, num := range nums {
sumMax += int64(maxRight[i]-i) * int64(i-maxLeft[i]) * int64(num)
sumMin += int64(minRight[i]-i) * int64(i-minLeft[i]) * int64(num)
}
return sumMax - sumMin
}
golang 解法, 执行用时: 20 ms, 内存消耗: 4.1 MB, 提交时间: 2022-11-29 11:57:36
func subArrayRanges(nums []int) (ans int64) {
for i, num := range nums {
minVal, maxVal := num, num
for _, v := range nums[i+1:] {
if v < minVal {
minVal = v
} else if v > maxVal {
maxVal = v
}
ans += int64(maxVal - minVal)
}
}
return
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 41.5 MB, 提交时间: 2022-11-29 11:57:20
/**
* @param {number[]} nums
* @return {number}
*/
var subArrayRanges = function(nums) {
const n = nums.length;
let ret = 0;
for (let i = 0; i < n; i++) {
let minVal = Number.MAX_VALUE, maxVal = -Number.MAX_VALUE;
for (let j = i; j < n; j++) {
minVal = Math.min(minVal, nums[j]);
maxVal = Math.max(maxVal, nums[j]);
ret += maxVal - minVal;
}
}
return ret;
};
python3 解法, 执行用时: 3780 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-29 11:56:35
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):
minVal = min(minVal, nums[j])
maxVal = max(maxVal, nums[j])
ans += maxVal - minVal
return ans