[LeetCode] 907. Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums/description/?envType=daily-question&envId=2024-01-20

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Sum of Subarray Minimums

문제 유형 : 다이나믹 프로그래밍, 단조 스택

문제 난이도 : Medium

 

 

문제

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로 나눈 나머지를 구하시오.

 

 

풀이

1차 시도: 처음에는 dp[i][j]로 하고, i~j인덱스로 만드는 부분배열의 최소값으로 계산을 하고, 2차원 루프를 돌렸더니, 시간초과가 나버렸다. O(n)내로 끝내야 한다.

 

dp[i] = i번째 인덱스를 마지막으로 하는 부분배열의 가장 작은 요소들의 합으로 하자.

스택도 하나 만든다. 여기에는 최소값의 인덱스를 저장시킨다.

배열을 순차적으로 탐색하면서, 스택에 있는 인덱스의 값이 이번 i번째의 숫자보다 큰 동안, 스택에서 요소를 제거한다.

그러면 i번째 인덱스보다 작은 값을 가진 요소가 남거나, 스택이 빈다.

만약 스택에 값이 남아서 i번째 인덱스보다 작은 값을 가진 요소가 있다면, 그 인덱스를 j로 둔다.

dp[i] = dp[j] + arr[i] * (i-j)이다.

만약 스택에 값이 없다면, 자신으로 끝나는 모든 부분배열에서 자신이 가장 작은 경우라는 뜻이니,

dp[i] = arr[i] *(i+1)이다.

 

아래 예시를 보자.

인덱스 1~3번이 스택에 값이 있는 경우이고, 0,4번은 스택이 빈 경우이다.

 

 

코드

C++

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int n = arr.size();
        const int MOD = 1e9+7;
        vector<int> dp(n, -1); // dp[i] = i로끝나는 부분배열의 최소값들의 합
        int sum = 0;
        stack<int> stk;


        for(int i = 0; i < n; i++) {
            while(!stk.empty() && arr[i]<=arr[stk.top()]) {
                stk.pop();
            }
            if(!stk.empty()) {
                int j = stk.top();
                dp[i]=dp[j]+arr[i]*(i-j);
            } else {
                dp[i] = arr[i]*(i+1);
            }
            stk.push(i);
            sum=(sum+dp[i])%MOD;
        }

        return sum;
    }
};