[leetcode]Sum of Subarray Minimums
原題
Given an array of integersA
, 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)
原題：ofollow,noindex">https://leetcode.com/problems/sum-of-subarray-minimums/
Github 原始碼：