[LeetCode]Sum of Subarray Minimums

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

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

题解

首先明确题意,给一个一维整形数组,要求求出其所有子序列(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


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。