엔지니어 게시판
LeetCode 솔루션 분류

[11/25] 907. Sum of Subarray Minimums

작성자 정보

  • 학부유학생 작성
  • 작성일

컨텐츠 정보

본문

Medium
4496302Add to ListShare

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 109 + 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 * 104
  • 1 <= arr[i] <= 3 * 104
Accepted
105,123
Submissions
305,819
태그

관련자료

댓글 1

학부유학생님의 댓글

  • 작성일
Runtime: 1247 ms, faster than 43.50% of Python3 online submissions for Sum of Subarray Minimums.
Memory Usage: 18.8 MB, less than 83.15% of Python3 online submissions for Sum of Subarray Minimums.
class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9+7
        res = 0
        stack = []
        arr = [0] + arr + [0]
        for idx, num in enumerate(arr):
            while stack and arr[stack[-1]] > num:
                curr = stack.pop()
                res += arr[curr]*(idx-curr)*(curr-stack[-1])
            stack.append(idx)
        
        return res%MOD
전체 307 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 36 명
  • 오늘 방문자 802 명
  • 어제 방문자 2,154 명
  • 최대 방문자 2,154 명
  • 전체 회원수 451 명
알림 0