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
Was this helpful?