内容简介:Given an array of integersSince the answer may be large,首先明确题意,给一个一维整形数组,要求求出其所有子序列(subarrays)中最小值的总和。且提示,结果可能很大,可以进行取模运算。
原题
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
题解
首先明确题意,给一个一维整形数组,要求求出其所有子序列(subarrays)中最小值的总和。且提示,结果可能很大,可以进行取模运算。
因为要求解每种子序列的最小值,即当前 子结构的最优解(最优子结构) ,且可以看出某个子序列的解可能会被包含其子序列的更大序列用到,即有 重叠子问题 性质。所以,可以考虑用动态规划策略来求解。
在求解问题时,首先想到了下面提到的“糟糕的动态规划”,但是分别面临了内存和时间溢出的尴尬;随后,在网友的题解中,了解到了下面“动态规划 & 单调栈”的策略。
糟糕的动态规划
递推关系
// i(从1开始计数) 指向当前元素的指针 // j(从1开始计数) 从i位置开始,向左跨越(j - 1)个元素 // d[i][j] 代表从第i个元素开始,向左跨越(j - 1)个元素的子序列中最小的值 // {2, 1, 2, 4, 2, 4} // 举例: i = 4,j = 3, 那么dp[i][j]就是{1, 2, 4}子序列的最小值即1 // 那么有如下递推关系(状态转移方程) dp[i][j] = A[i - 1]; // j == 1 && i == 1 dp[i][j] = min(A[i - 1], dp[i - 1][j - 1]); // j > 1 && i > 1
代码
class Solution { public: int sumSubarrayMins(vector<int>& A) { int mod = 1000000007; map<int, map<int, int>> dp; map<int, map<int, int>>::iterator it; map<int, int>::iterator itt; int sum = 0, c_min; for (int i = 1; i <= (int)A.size(); i++) { for (int j = 1; j <= i; j++) { if (j == 1) { map<int, int> sub_map; c_min = A[i - 1]; sub_map.insert(make_pair(j, c_min)); dp.insert(make_pair(i, sub_map)); //dp[i][j] = A[i - 1]; } else { it = dp.find(i - 1); itt = (it->second).find(j - 1); c_min = min(A[i - 1], itt->second); it = dp.find(i); (it->second).insert(make_pair(j, c_min)); dp.insert(make_pair(i, it->second)); //dp[i][j] = min(A[i - 1], dp[i - 1][j - 1]); } sum = (sum + c_min) % mod; } } return sum; } };
复杂度分析
时间复杂度:O(nlgn)
空间复杂度:O(nlgn)
上述方式耗时比较久,导致了超时错误。
动态规划 & 单调栈
为了减少时间复杂度,从状态转移方程入手,如果将上述dp数组从二维的转变为一维的,那么时间就有可能降到O(n)。
如果是一维的,那么dp[i](这次i从0计数)代表的就是第(i+1)元素作为最右端,其包含的所有向左的子序列的最小值的和。如下:
// {2, 1, 2, 4, 2, 4} // dp[3] 代表的左右子序列中最小值之和,即子序列:{4} {2, 4} {1, 2, 4} {2, 1, 2, 4} // 子列中最小值的和 即4 + 2 + 1 + 1 = 8 // 故 dp[3] = 8
递推关系
那么如果求解dp[3]呢?可以发现一个规律,找到其代表的最长子序列中最小值——1,其最小值索引用j(从0开始计数)代表。并拿到当前元素距离最小值的距离d = i - j。
那么可以得到,如下状态转移方程:
// d = i - j 即 j = i - d dp[i] = A[i]; // i == 1 dp[i] = A[i] * d + dp[i - d]; // i > 1
那么现在的问题就是如果获取这个d,从上面可以看到我们只有知道当前元素向左看,其中最小值的索引(j)才能知道d的值。那么这个d的值,可以用单调栈数据结构来维护。
这个栈从头(top)到尾(tail)看是单调递增的,如下秒速一个动态压栈的过程,来看看单调栈是如何维护这个j值的。
// {2, 1, 2, 4, 2, 4} // // i = 0 栈(头->尾):{[2, 1]} // 其中2代表A[i]元素的值,1代表的是 当前元素作为最小值的情况,向左的子序列的最大长度 // // i = 1 栈(头->尾):{[1, 2]} 发现,[2, 1]元素没有了 // 是因为压栈时为了保持从头到尾单调递减的性质,把之前的元素pop,并将其距离自增1 // // i = 2 栈(头->尾):{[2,1], [1, 2]}
代码
class Solution { stack<pair<int, int>> st; public: int next(int price) { int d = 1; while (!st.empty() && st.top().first >= price) { d += st.top().second;; st.pop(); } st.push(make_pair(price, d)); return d; } int sumSubarrayMins(vector<int>& A) { int a = 0, l = A.size(), d, mod = 1000000007; int dp[A.size()]; for (int i = 0; i < l; i++) { d = next(A[i]); //dp[i] = A[i] * d + dp[i - d]; dp[i] = (A[i] * d) % mod; if (i - d >= 0) dp[i] = (dp[i] + dp[i - d]) % mod; a = (a + dp[i]) % mod; } return a; } };
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n)
原题: https://leetcode.com/problems/sum-of-subarray-minimums/
Github 源码:
文章来源: 胡小旭 => [leetcode]Sum of Subarray Minimums
以上所述就是小编给大家介绍的《[leetcode]Sum of Subarray Minimums》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
PHP and MySQL Web Development
Luke Welling、Laura Thomson / Sams / July 25, 2007 / $49.99
Book Description PHP and MySQL Web Development teaches you to develop dynamic, secure, commerical Web sites. Using the same accessible, popular teaching style of the three previous editions, this b......一起来看看 《PHP and MySQL Web Development》 这本书的介绍吧!