Leetcode 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이 주어졌을때, arr에서 만들수 있는 모든 부분 배열에 대해 그에 해당하는 최솟값이 존재한다.
그 최솟값들의 합을 구하시오.
값이 너무 크면 10^9 + 7 로 나머지 연산하여 리턴하라

예시

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
모든 가능한 부분 배열은 오른쪽과 같다. [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
이들의 최솟값은 3, 1, 2, 4, 1, 1, 2, 1, 1, 1 이고,
이들의 합은 17이다.

제한

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

풀이법

1. 최소값에 들어갈수 있는 갯수

[2, 1, 3, 4] 의 예시에서 1이 들어갈수 있는 부분배열의 갯수는 다음과 같다.

• 1의 왼쪽에 1보다 작은 숫자들의 갯수는 1개이다 ( 2 )
• 1의 오른쪽에 1보다 작은 숫자들의 갯수는 2개이다 ( 3 , 4 )
• 왼쪽의 숫자들을 포함하는 부분배열은 2개이다 ( [1], [2, 1] )
• 오른쪽의 숫자들을 포함하는 부분배열은 왼쪽을 포함하는 배열의 갯수 * 오른쪽의 작은 숫자 갯수이다.

풀이

• 위를 이용해 왼쪽에 자신보다 작은 갯수와 오른쪽에 자신보다 작은 갯수를 구해 찾으면 된다.

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10 ** 9 + 7
        res = 0
        stack = []

        for i, n in enumerate(arr):
        # 스택에 숫자를 쌓다가 왼쪽에 자신보다 큰 숫자가 있을경우 이 숫자는 빼낸다.
            while stack and n < stack[-1][1]:
                j, m = stack.pop()
                left = j - stack[-1][0] if stack else j + 1
                right = i - j
                res = (res + m * left * right) % MOD
            stack.append((i, n))

        for i in range(len(stack)):
            j, n = stack[i]
            left = j - stack[i - 1][0] if i > 0 else j + 1
            right = len(arr) - j
            res = (res + n * left * right) % MOD

        return res