907. Sum of Subarray Minimums

• 주어진 배열 $arr$ 의 모든 연속된 부분 배열 $A_{ij} = [\,arr[i], \,arr[i+1], \, ..., \, arr[j]\,] \,\, (0 ≤ i ≤ j < N)$에 대해서 그 최소값 $min(A_{ij})$의 합 $S = \sum\limits_{i=0}^{N-1}\sum\limits_{j=i}^{N-1}\,min(A_{ij})$ 을 구하는 문제.
• 결과 값이 매우 클 수 있으므로 $10^9 + 7$로 나머지 연산을 수행해서 돌려주어야 한다.

• 단순하게 접근한다면 각 범위 $[i, j]$ 별로 최소값을 구하는 방식을 취할 수 있을 것이다. 다만 이렇게 하면 시간 복잡도가 $O(N^2)$이 되므로 시간 제한을 초과하게 된다.

• 배열을 한번만 순회하면서 값을 계산하기 위해서 부분 배열의 최소값 규칙을 발견할 필요가 있다.

e.g. arr = [3, 2, 4, 1] 이라고 가정하자. 각 부분 배열 별 최소값을 구하면 아래와 같다.

- index = 0
  - sub array: [3], [3, 2], [3, 2, 4], [3, 2, 4, 1]
  - min value:  3,   2,      2,         1
- index = 1
  - sub array:      [2],    [2, 4],    [2, 4, 1]
  - min value:       2,      2,         1
- index = 2
  - sub array:              [4],       [4, 1]
  - min value:               4,         1
- index = 3
  - sub array:                         [1]
  - min value:                          1

• 위의 결과로 부터 다음과 같은 로직을 도출할 수 있다.
• 배열 $arr$에 출현한 값을 하나씩 순회하면서 새로운 배열 $arr’$에 넣는다.
• 현재 값 $a_i = arr[i]$에 대하여,
• $arr’$에 있는 값 중 $a_i$ 보다 큰 모든 값은 $a_i$로 대체한다.
• $arr’$에 있는 값 중 $a_i$ 보다 작은 모든 값은 그대로 둔다.
• $arr’$에 값을 하나 넣을 때 마다 $arr’$에 있는 모든 값을 결과 값에 더한다.

• 로직 수행했을 때 $arr’$의 상태을 시각화하면 아래와 같다.

e.g. arr = [3, 2, 4, 1] 이라고 할 때,

- index = 0 → [3]
- index = 1 → [3 → 2, 2] → [2, 2]
- index = 2 → [2, 2, 4]
- index = 3 → [2 → 1, 2 → 1, 4 → 1, 1] → [1, 1, 1, 1]

• $arr’$의 값을 저장하기 위해서 스택을 사용하면 위의 로직을 쉽게 구현할 수 있다.
• 문제는 스택을 사용했을 때 모든 값을 순회하면서 더한다면 최악의 경우에는 시간 복잡도가 $O(N^2)$이 될 수 있다.
• $arr$의 값이 단조 증가 $a_i ≤ a_j \, (i < j)$ 할 경우 제거되는 값이 없이 모든 값이 스택에 추가되므로 스택의 크기는 $O(N)$이 되기 때문이다.
• 매 index 마다 $O(N)$의 시간 복잡도로 값을 더해야 하기에 결과적으로 시간 복잡도는 $O(N^2)$가 된다.

• 따라서 스택에 들어가 있는 값의 합을 별도의 메모리 currSum로 추적한다면 이 시간을 아낄 수 있다.
• 새롭게 값이 추가되면 currSum에 더한다.
• 기존에 있는 값을 제거할 때는 currSum에서 뺀다.

• 또한 동일한 값을 스택에 각각 넣는 대신, 숫자 & 해당 숫자의 출현 빈도를 저장하는 것이 좋을 것이다.

e.g. arr = [3, 2, 4, 1] 이라고 할 때, 스택에 [숫자, 숫자의 출현 빈도] 로 저장한다.

<바꾸기 전>
- index = 0 → [3]
- index = 1 → [2, 2]
- index = 2 → [2, 2, 4]
- index = 3 → [1, 1, 1, 1]

<바꾼 후>
- index = 0 → [[3, 1]]
- index = 1 → [[2, 2]]
- index = 2 → [[2, 2], [4, 1]]
- index = 3 → [[1, 4]]

class Solution {
    public static final int MOD = 1_000_000_000 + 7;
    
    public int sumSubarrayMins(int[] arr) {
        int N = arr.length;
        Stack<int[]> stack = new Stack<>();
        int currSum = arr[0];
        int sum = currSum;
        stack.push(new int[]{ arr[0], 1 });
        for (int i = 1; i < N; ++i) {
            int count = 1;
            while (!stack.empty()) {
                int[] last = stack.peek();
                if (last[0] < arr[i]) break;

                stack.pop();
                count += last[1];
                currSum = (currSum - last[0] * last[1]) % MOD;
            }

            int[] newPair = new int[]{ arr[i], count };
            stack.push(newPair);

            currSum = (currSum + newPair[0] * newPair[1]) % MOD;
            sum = (sum + currSum) % MOD;
        }
        return sum;
    }
}