Description#
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:
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.
Example 2:
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.
Example 3:
Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: The sum of all subarray ranges of nums is 59.
Constraints:
1 <= nums.length <= 1000-109 <= nums[i] <= 109
Follow-up: Could you find a solution with O(n) time complexity?
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
ans, n = 0, len(nums)
for i in range(n - 1):
mi = mx = nums[i]
for j in range(i + 1, n):
mi = min(mi, nums[j])
mx = max(mx, nums[j])
ans += mx - mi
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public long subArrayRanges(int[] nums) {
long ans = 0;
int n = nums.length;
for (int i = 0; i < n - 1; ++i) {
int mi = nums[i], mx = nums[i];
for (int j = i + 1; j < n; ++j) {
mi = Math.min(mi, nums[j]);
mx = Math.max(mx, nums[j]);
ans += (mx - mi);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
long long ans = 0;
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
int mi = nums[i], mx = nums[i];
for (int j = i + 1; j < n; ++j) {
mi = min(mi, nums[j]);
mx = max(mx, nums[j]);
ans += (mx - mi);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func subArrayRanges(nums []int) int64 {
var ans int64
n := len(nums)
for i := 0; i < n-1; i++ {
mi, mx := nums[i], nums[i]
for j := i + 1; j < n; j++ {
mi = min(mi, nums[j])
mx = max(mx, nums[j])
ans += (int64)(mx - mi)
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function subArrayRanges(nums: number[]): number {
const n = nums.length;
let res = 0;
for (let i = 0; i < n - 1; i++) {
let min = nums[i];
let max = nums[i];
for (let j = i + 1; j < n; j++) {
min = Math.min(min, nums[j]);
max = Math.max(max, nums[j]);
res += max - min;
}
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| impl Solution {
pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
let n = nums.len();
let mut res: i64 = 0;
for i in 1..n {
let mut min = nums[i - 1];
let mut max = nums[i - 1];
for j in i..n {
min = min.min(nums[j]);
max = max.max(nums[j]);
res += (max - min) as i64;
}
}
res
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
def f(nums):
stk = []
n = len(nums)
left = [-1] * n
right = [n] * n
for i, v in enumerate(nums):
while stk and nums[stk[-1]] <= v:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] < nums[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(nums))
mx = f(nums)
mi = f([-v for v in nums])
return mx + mi
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public long subArrayRanges(int[] nums) {
long mx = f(nums);
for (int i = 0; i < nums.length; ++i) {
nums[i] *= -1;
}
long mi = f(nums);
return mx + mi;
}
private long f(int[] nums) {
Deque<Integer> stk = new ArrayDeque<>();
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
left[i] = stk.peek();
}
stk.push(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
while (!stk.isEmpty() && nums[stk.peek()] < nums[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
right[i] = stk.peek();
}
stk.push(i);
}
long s = 0;
for (int i = 0; i < n; ++i) {
s += (long) (i - left[i]) * (right[i] - i) * nums[i];
}
return s;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
long long mx = f(nums);
for (int i = 0; i < nums.size(); ++i) nums[i] *= -1;
long long mi = f(nums);
return mx + mi;
}
long long f(vector<int>& nums) {
stack<int> stk;
int n = nums.size();
vector<int> left(n, -1);
vector<int> right(n, n);
for (int i = 0; i < n; ++i) {
while (!stk.empty() && nums[stk.top()] <= nums[i]) stk.pop();
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!stk.empty() && nums[stk.top()] < nums[i]) stk.pop();
if (!stk.empty()) right[i] = stk.top();
stk.push(i);
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans += (long long) (i - left[i]) * (right[i] - i) * nums[i];
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| func subArrayRanges(nums []int) int64 {
f := func(nums []int) int64 {
stk := []int{}
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := range left {
left[i] = -1
right[i] = n
}
for i, v := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] <= v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && nums[stk[len(stk)-1]] < nums[i] {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
ans := 0
for i, v := range nums {
ans += (i - left[i]) * (right[i] - i) * v
}
return int64(ans)
}
mx := f(nums)
for i := range nums {
nums[i] *= -1
}
mi := f(nums)
return mx + mi
}
|
