2104. Sum of Subarray Ranges
Last updated
Last updated
sum = sum(max) - sum(min) -> this is the point!
because nextLarger and prevLarger , prevSmaller, nextSmaller just help us find left bound , right bound
for min, or for max
but we don't know the paired min max how to map to each other (from nextLarger and prevLarger , prevSmaller, nextSmaller
but we need to cal max - min in this subarray's max min pair
seems hard to use range
T: O(n)
S: O(n)
class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
int[] prevSmaller = new int[n];
int[] nextSmaller = new int[n];
int[] prevGreater = new int[n];
int[] nextGreater = new int[n];
Arrays.fill(nextSmaller, n);
Arrays.fill(prevSmaller, -1);
Arrays.fill(nextGreater, n);
Arrays.fill(prevGreater, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
nextSmaller[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
stack.clear();
for (int i = n-1; i >= 0; i--) {
while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
prevSmaller[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
stack.clear();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
nextGreater[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
stack.clear();
for (int i = n-1; i >= 0; i--) {
while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
prevGreater[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
long result = 0L;
// between nextGreater and prevGreater => max
// between nextSmaller and prevSmaller => min
// max - min
for (int i = 0; i < n; i++) {
result += (long)(nextGreater[i] - i)*(i - prevGreater[i])*nums[i] - (long)(nextSmaller[i] - i)*(i - prevSmaller[i])*nums[i];
}
return result;
}
}
/*
range:
the difference between the largest and smallest element in the subarray.
return sum of all in this range
[1,2,3]
[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.
if nums[i] is min => the range: prevSmaller: l and nextSmaller; r
nums[i]*(i-l)*(r-i)
if nums[i] is max : b => the range: prevGreater and nextGreater
nums[i]*(i-l)*(r-i)
result += nums[i]*(i-l)*(r-i)
result -= nums[i]*(i-l)*(r-i)
nums[i]*(i-l)*(r-i)
->
(i-l)*(r-i)
iįåˇĻéæåšžåæ¸
åŗéæåšžåæ¸, į¸äščĩˇäžå°ąæ¯į¸Ŋå
ąåæ¸
ex: 1,2,3
max:
nextLarger: [1, 2, 3]
prevLarger: [-1, -1, -1]
įļi = 0, nums = 1
(r - i) * (i - l)
(1 - 0) * (0 -(-1)
-> 1*1 = 1
åžé襨äšå¯äģĨįåē max 1, äšåĒæä¸æŦĄ
[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
čäž num = 3äžčĒĒ, i = 2
nextLarger: [1, 2, 3]
prevLarger: [-1, -1, -1]
(3 - 2) * (2 - (-1))
= 1* 3 = 3
num = 3 äšįįĸēåēįž max 3 æŦĄ (subarray å
§åēįž 3æŦĄ
i
-1. 2. 3
*/class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
int[] nextSmaller = new int[n];
int[] prevSmaller = new int[n];
int[] nextLarger = new int[n];
int[] prevLarger = new int[n];
Arrays.fill(nextSmaller, n);
Arrays.fill(nextLarger, n);
Arrays.fill(prevSmaller, -1);
Arrays.fill(prevLarger, -1);
Deque<Integer> stack = new ArrayDeque<>();
// nextSmaller īŧ [3,1,2]
/*
(then 1 , has nextSmaller , record it! ->nextSmaller[0] = 1 , then pop
0 (3
*/
for (int i = 0; i < n ; i++) {
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
nextSmaller[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
stack.clear();
// prevSmaller, avoid duplicate , we want left one, so when new number == stack number, we keep record it
for (int i = n-1; i >= 0 ; i--) {
while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
prevSmaller[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
stack.clear();
// nextLarger
for (int i = 0; i < n ; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
nextLarger[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
stack.clear();
// prevLarger, avoid duplicate , we want left one, so when new number == stack number, we keep record it
for (int i = n-1; i >= 0 ; i--) {
while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
prevLarger[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
long result = 0L;
for (int i = 0; i < n; i++) { // notice the long tupe
result += (long)nums[i]*(nextLarger[i] - i)*(i - prevLarger[i]) - (long)nums[i]*(nextSmaller[i] - i)*(i - prevSmaller[i]);
}
return result;
}
}
/*
1. brute force
find all subarrays, T: o(n^2), count of subarray -> T: O(n^2), find max, min, -> T: O(n^2*n) -> O(n^3)
2. how to avoid find all subarray
think of each elemnt as the min -> find the left, right bound. it means
ex: [1,2,3]
1 as min -> [1,2,3] ->with this range, all subarrays' min is 1
...
how to find right bound?
use monostack find
nextSmaller [n, n, n] -> this array we will record each emlent's next smaller [n, n, n]
find left bound
prevSmaller [-1, -1, -1] -> this array we will record each emlent's prev smaller, from end [-1, 0, 1]
(index -> 3's next prev smaller num , index is 1 (nums[1] = 2) )
[n, n, n]
[-1, 0, 1]
for index 0 (1) -> range is -1 to n (äģĨ num 1 įē min įindexį¯å) -> [1,2,3] -> in these subarrays (3 subarrays), the min is 1 -> sum(min of these subarrays) => 3*1= 3
-1 0 1 2 n
[1,2,3]
for index 1 (2) -> range is 0 to n (äģĨ num 2 įē min įindexį¯å)-> [2,3] (2 subarrays), min is 2, 2*2=4
0 1 2 n
[1,2,3]. range (0 to n) -> å°ąæ¯ index 1, 2 -> [2, 3]
for index 2 (3) -> range is 1 to n (äģĨ num 3 įē min įindexį¯å)-> [3] (1 subarray), min is 3, 3*1 = 3
1 2 n
[1,2,3]. range (1 to n) -> å°ąæ¯ index 2 -> [3]
sum them up -> all min sum = 10
in example,
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
-> min: 1 åēįžäē 3 æŦĄ, 2 åēįž 2 æŦĄ, 3 åēįž 1æŦĄ, čˇæååéĸįč¨įŽį¸įŦĻ
we can see, actually, the ans is sum(max) - sum(min) -> we don't need to cal diff in each subarray
so we cal the sum(max)
result = sum(max) - sum(min)
T: O(n)
duplicate case,
why duplicate case will cause error?
[5,3,3,3,6]
^ ^ ^
these 3's range are same , so 3 subarrays are the same
æåå¯äģĨį´åŽæåŗéįéč¤æ¯æåčĻįæå°åŧ
å¨ nextSmaller æåä¸įŽĄ [1,3,3,3,2] => index 1's 3 is min the range is
we handle this in prevSmaller
[]
[1,3,3,3,1]
[-1,-1,-1,-1,-1]
find left bound if smaller or equal -> we find the left bound
for this 3
[1,3,3,3,1]
^
f -> here we find the left bound
like this
[1,3,3,[3,1]]
index 2 3 ->equal!!
index 3 3 -> record prevSmaller[3] = 2
index 4 1
*/ja
duplicate case,
why duplicate case will cause error?
[5,3,3,3,6]
^ ^ ^
these 3's range are same , so 3 subarrays are the same
æåå¯äģĨį´åŽæåŗéįéč¤æ¯æåčĻįæå°åŧ
æäģĨ 3 [8 4 4 8 4]
īŧž
éåæåŗéį 4ææ¯æåį right bound
left bound å°ąå¯äģĨæ4įéč¤ æäģĨå¯äģĨä¸čˇ¯å° 8
äŊ right bound å°ąä¸čĄåæéč¤äē
3 [8 4 4 8 4] 4
^
æäģĨåéæ¨Ŗ right bound å°ąæ¯å° ^ éčŖĄ
æäģĨ left bound æåå¯äģĨ <=
äŊ right bound æ¯ <
----------------
ååå°åæŦįäžį
[8 4 4 8 4]
=> åĻæä¸čį äģĨ 4įēminåģæžæ, éčŖĄå°ąææä¸åä¸æ¨Ŗį subarray éŊæ¯ [8 4 4 8 4]
æäģĨį´åŽæåŗéį 4 æ¯æåčĻį, left bound <=, right bound <
æäģĨ į index 1 į4æ(įŦŦ1å4)
[8 4 4 8 4]
=> ææ¯ [8,4]
į index 2 į4æ(įŦŦ2å4)
[8 4 4 8 4]
=> ææ¯ [4]
į index 3 į4æ (įŦŦ3å4)
[8 4 4 8 4]
=> ææ¯ [8 4 4 8 4]
åĻæ¤å°ąå¯äģĨč§Ŗæąēéč¤įåéĄīŧ
