# Leetcode --- Sum of Subarray Minimums

## 907. Sum of Subarray Minimums
### Description:
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.

:::info
Example :
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.
:::
:::warning
此題的子陣列為連續型態, 因此總共只有n^2^個子陣列。
:::
### 解法條列
1. 暴力解 O(n^3^)
2. 優化解 O(n)

### 解法細節
找出所以元素的左右小於元素索引位置, 即可用這兩個索引值計算該元素距離左右範圍, 會在幾個subset內為最小值, 並將之subset數乘上自身。

為了在線性時間O(n)找出所有左右索引, 使用資料結構:
:::success
monotonic stack
:::

### Python Solution
優化解

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        left_index_stack = [0 for _ in range(len(arr))]
        right_index_stack = [0 for _ in range(len(arr))]
        index_stack = []
        # 找出右邊的小於值
        for i,num in enumerate(arr):
            while(index_stack and arr[index_stack[-1]] >= num):
                tmp = index_stack.pop()
                right_index_stack[tmp] = i - tmp - 1
            index_stack.append(i)
        while(index_stack):
            temp = index_stack.pop()
            right_index_stack[temp] = len(arr) - temp - 1 
            
        # 找出左邊的小於值
        index_stack = []
        i = len(arr)-1
        while(i >= 0):
            while(index_stack and arr[index_stack[-1]] >  arr[i]):
                tmp = index_stack.pop()
                left_index_stack[tmp] = tmp - i - 1
            index_stack.append(i)
            i -= 1
        while(index_stack):
            temp = index_stack.pop()
            left_index_stack[temp] =  temp

        # 利用找出的左右小於值距離計算
        ans = 0
        for i in range(len(arr)):
            ans += ((left_index_stack[i]+1)*(right_index_stack[i]+1)*arr[i])
        return ans%(10**9 + 7)
            

---

left_index_stack = [0 for _ in range(len(arr))]
right_index_stack = [0 for _ in range(len(arr))]
index_stack = []

left_index_stack和right_index_stack用來存放對應索引值的左右距離
index_stack則是作為monotic stack來找出索引值位置

---

# 找出右邊的小於值
for i,num in enumerate(arr):
    while(index_stack and arr[index_stack[-1]] >= num):
        tmp = index_stack.pop()
        right_index_stack[tmp] = i - tmp - 1
    index_stack.append(i)
while(index_stack):
    temp = index_stack.pop()
    right_index_stack[temp] = len(arr) - temp - 1 

這裡需要注意的是第7行的while迴圈,會處理在index_stack中的元素, 也就是沒有找到右邊有比較小的值.
可能因素有兩個:
1. 右邊沒有元素比較小
2. 右邊沒有其他元素了

因此為了正確紀錄距離，利用陣列長度以及其所在位置算出右邊的元素數量。

---

# 利用找出的左右小於值距離計算
ans = 0
for i in range(len(arr)):
    ans += ((left_index_stack[i]+1)*(right_index_stack[i]+1)*arr[i])
return ans%(10**9 + 7)

利用左右距離計算並加總

---
可改進部分為時間可以再縮短, 精簡操作的次數, 將程式碼合併起來。

###### tags: `leetcode` `array` `medium` `stack` `monotic stack`