[Swift]LeetCode907.子数组的最小值之和|SumofSubarrayMinimums

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 <= A.length <= 30000
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 <= A <= 30000
1 <= A[i] <= 30000

Runtime: 524 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func sumSubarrayMins(_ A: [Int]) -> Int {
 3         var stack:[Int] = [Int]()
 4         var n:Int = A.count
 5         var res:Int = 0
 6         var mod:Int = Int(1e9 + 7)
 7         var j:Int = 0
 8         var k:Int = 0
 9         for i in 0...n
10         {
11             while (!stack.isEmpty && A[stack.last!] > (i == n ? 0 : A[i]))
12             {
13                 j = stack.removeLast()
14                 k = stack.isEmpty ? -1 : stack.last!
15                 res = (res + A[j] * (i - j) * (j - k)) % mod
16             }
17             stack.append(i)
18         }
19         return res
20     }
21 }

608ms

 1 class Solution {
 2     func sumSubarrayMins(_ A: [Int]) -> Int {
 3         let m = 1000000007
 4         let A = A + [Int.min]
 5         var ascend = [Int]()
 6         var res = 0
 7         for i in 0..<A.count {
 8             while !ascend.isEmpty && A[ascend.last!] > A[i] {
 9                 let k = ascend.popLast()!
10                 let j = ascend.last ?? -1
11                 res += A[k] * (i - k) * (k - j)
12             }
13             res = res % m
14             ascend.append(i)
15         }
16         return res
17     }
18 }

12108ms

 1 class Solution {
 2     func sumSubarrayMins(_ A: [Int]) -> Int {
 3         if A.isEmpty {
 4             return 0
 5         }
 6         
 7         let n = A.count, MOD = 1000000007
 8         var s = [Int]()
 9         // sum of subarray mins ending with A[i]
10         var dp = [Int](repeating: 0, count: n) 
11         // 3 1 2 4 5 1
12         for i in 0..<n {
13             dp[i] = (dp[i] + A[i]) % MOD
14             if i == 0 {
15                 continue
16             }
17             if A[i-1] < A[i] {
18                 dp[i] = (dp[i] + dp[i-1]) % MOD
19             } else {
20                 var j = i-1
21                 while j >= 0 && A[j] > A[i] {
22                     j -= 1
23                 }
24                 dp[i] = (dp[i] + A[i] * (i-j-1)) % MOD
25                 if j >= 0 {
26                     dp[i] = (dp[i] + dp[j]) % MOD
27                 }
28             }
29         }
30         var res = 0
31         for sum in dp {
32             res = (res + sum) % MOD
33         }
34         return res
35     }
36 }