[Swift]LeetCode907. 子数组的最小值之和 | Sum of Subarray Minimums

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10609813.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7. 

Example 1:

Input: [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. 

Note:

1. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

---

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

由于答案可能很大，因此返回答案模 10^9 + 7。 

示例：

输入：[3,1,2,4]
输出：17
解释：
子数组为 [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. 1 <= A <= 30000
2. 1 <= A[i] <= 30000

---

Runtime: 524 ms

Memory Usage: 19 MB

class Solution {
    func sumSubarrayMins(_ A: [Int]) -> Int {
        var stack:[Int] = [Int]()
        var n:Int = A.count
        var res:Int = 0
        var mod:Int = Int(1e9 + 7)
        var j:Int = 0
        var k:Int = 0
        for i in 0...n
        {
            while (!stack.isEmpty && A[stack.last!] > (i == n ? 0 : A[i]))
            {
                j = stack.removeLast()
                k = stack.isEmpty ? -1 : stack.last!
                res = (res + A[j] * (i - j) * (j - k)) % mod
            }
            stack.append(i)
        }
        return res
    }
}

---

608ms

class Solution {
    func sumSubarrayMins(_ A: [Int]) -> Int {
        let m = 1000000007
        let A = A + [Int.min]
        var ascend = [Int]()
        var res = 0
        for i in 0..<A.count {
            while !ascend.isEmpty && A[ascend.last!] > A[i] {
                let k = ascend.popLast()!
                let j = ascend.last ?? -1
                res += A[k] * (i - k) * (k - j)
            }
            res = res % m
            ascend.append(i)
        }
        return res
    }
}

---

12108ms

class Solution {
    func sumSubarrayMins(_ A: [Int]) -> Int {
        if A.isEmpty {
            return 0
        }
        
        let n = A.count, MOD = 1000000007
        var s = [Int]()
        // sum of subarray mins ending with A[i]
        var dp = [Int](repeating: 0, count: n) 
        // 3 1 2 4 5 1
        for i in 0..<n {
            dp[i] = (dp[i] + A[i]) % MOD
            if i == 0 {
                continue
            }
            if A[i-1] < A[i] {
                dp[i] = (dp[i] + dp[i-1]) % MOD
            } else {
                var j = i-1
                while j >= 0 && A[j] > A[i] {
                    j -= 1
                }
                dp[i] = (dp[i] + A[i] * (i-j-1)) % MOD
                if j >= 0 {
                    dp[i] = (dp[i] + dp[j]) % MOD
                }
            }
        }
        var res = 0
        for sum in dp {
            res = (res + sum) % MOD
        }
        return res
    }
}