2104. Sum of Subarray Ranges
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
*/more concise
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
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]
ๅฆๆญคๅฐฑๅฏไปฅ่งฃๆฑบ้่ค็ๅ้ก๏ผ
Last updated
