[LeetCode][Kotlin] 907. Sum of Subarray Minimums

907. Sum of Subarray Minimums

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.

정수 arr의 배열이 주어졌을 때, b가 arr의 모든 (인접한) 부분 배열에 걸쳐 있는 min(b)의 합을 구하세요. 답이 클 수 있으므로 답을 10^9 + 7로 나눈 나머지로 반환합니다.

 

Example 1:

Input: arr = [3,1,2,4]

Output: 17

Explanation: 

Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 

Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.

Sum is 17.

 

Example 2:

Input: arr = [11,81,94,43,3]

Output: 444

 

Constraints:

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 3 * 10^4

---

코드

• Example 1 : [3] / [4] / [2], [2, 4] / [1], [1, 2], [1, 2, 4], [3, 1], [3, 1, 2], [3, 1, 2, 4]

class Solution {
    fun sumSubarrayMins(arr: IntArray): Int {
        val MOD = 1_000_000_007
        var res = 0L
        val newArr = intArrayOf(Int.MIN_VALUE) + arr + intArrayOf(Int.MIN_VALUE)
        val stack = mutableListOf<Pair<Int, Int>>()

        for ((i, n) in newArr.withIndex()) {
            while (stack.isNotEmpty() && n < stack.last().second) {
                val (j, m) = stack.removeLast()
                val left = j - if (stack.isNotEmpty()) stack.last().first else j + 1
                val right = i - j
                res = (res + m.toLong() * left * right) % MOD
            }
            stack.add(i to n)
        }

        return res.toInt()
    }
}