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]
  
  如此就可以解決重複的問題！