算法leetcode

带大小限制的最大子数组/子矩阵和

字数统计: 2.5k字   |   阅读时长: 10分
, , ,

摘要: 带大小限制的最大子矩阵和

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解法，都非常主流，并且各个方法都有它适用的变种问题。

在文章 环形数组上的最大子数组和 和文章 最大子矩阵和 中，我们看了两类最直接的变种：第一个是把数组变成环形数组，那道题的重点是怎样把环形数组上的问题转换为普通数组上的问题。只要完成了正确的转换，就可以套用普通数组上我们已经知道的解法；第二个是把数组变成矩阵，那道题的重点是怎样把二维上的问题转化为一维上的问题，只要能正确转化，就可以套用一维上的已知解法来解决。

本文我们看另一类变种：对求和的过程增加限制，题目是力扣 363，带大小限制的最大子矩阵和。在本题中，我们首先将二维的问题转化为一维的问题，然后解决带大小限制的最大子数组和。

带大小限制的最大子数组和有两种算法，分别是平衡树和双指针。

题目: 带大小限制的最大子矩阵和问题

363. 矩形区域不超过 K 的最大数值和

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

提示：

1
2
3
4
5
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-1e5 <= k <= 1e5

样例

示例 1：
输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例 2：
输入：matrix = [[2,2,-1]], k = 3
输出：3

Follow Up:

如果行数远大于列数，该如何设计解决方案？

题解

算法: 转换为一维问题

本题的难点在于多了一个和不超过 K 的限制，如果没有这个限制，就是最大子矩阵和的问题。

对于最大子矩阵和的问题，可以枚举轴向 axis=1 上的所有区间 [j1, j2]，对于每个枚举的区间，在另一个轴向上 axis=0 可以直接调用一维的最大子数组和问题的算法。参考 最大子矩阵。

对于本题，依然可以枚举轴向 axis=1 上的所有区间 [j1, j2]，对于每个枚举的区间，在另一个轴向上的问题就是带大小限制的最大子段和的问题。

代码 (C++)

假设已经有了一个接口，实现了带大小限制的最大子段和的问题：

1
int maxSubArray(vector<int>& nums, int k);

那么枚举某一轴向的所有区间然后在另一个轴向上解决一维的问题的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size(), m = matrix[0].size();

        vector<vector<int>> sums(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + matrix[i][j];

        int ans = INT_MIN;
        vector<int> vec(n);
        for(int j1 = 0; j1 < m; ++j1)
            for(int j2 = j1; j2 < m; ++j2)
            {
                for(int i = 0; i < n; ++i)
                    vec[i] = rec_sum(i, j1, i, j2, sums);
                ans = max(ans, maxSubArray(vec, k));
            }

        return ans;
    }

private:
    int rec_sum(int i1, int j1, int i2, int j2, const vector<vector<int>>& sums)
    {
        // 左上角 (i1, j1), 右下角 (i2, j2)
        return sums[i2 + 1][j2 + 1] - sums[i2 + 1][j1] - sums[i1][j2 + 1] + sums[i1][j1];
    }

    int maxSubArray(vector<int>& nums, int k);
};

下面的问题就是解决带大小限制的最大子段和问题。

带大小限制的最大子段和问题

回顾: 用前缀和解决无限制的最大子数组和问题

将 A[0..n-1] 的前缀和 sums[0..n] 求出之后，枚举每个前缀和的下标 1 <= j <= n，找到 j - i <= N 时最大的 sums[j] - sums[i] 即为以 A[j - 1] 为结尾的最大子数组和，也就是要找最小的 sums[i]。

摊销 O(1) 地找到每个 j 的左侧最值及其下标 i，其中 i 的范围需要满足某些条件(这里是 j - i <= N)。这正是单调队列的场景。

1
2
a[0..i] 的和 sums[i+1] 求出后
问 sums[0..i] 的最小值是多少

这里问最值的区间左端点是没有限制的，一直是 0，当新下标 i 来的时候，只会在队尾弹出一些比 sums[i] 小的，而不会因为区间的限制从左边弹出下标。

这种不用从左边弹出下标的场景用单调队列有点多此一举，不过对于有长度限制的最大子段和，就需要用到单调队列的从左边弹出不满足区间限制的下标这个特性了，这个问题也是有的，我们以后再看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> sums(n + 1, 0);
    deque<int> deq;
    deq.push_back(0); // sums[0] = 0
    int ans = INT_MIN;
    for(int i = 0; i < n; ++i)
    {
        sums[i + 1] = sums[i] + nums[i];
        // 此时问：sums[0..i] 上的最小值 mx 是多少
        int  mx = sums[deq.front()];
        ans = max(ans, sums[i + 1] - mx);
        while(!deq.empty() && sums[deq.back()] >= sums[i + 1])
            deq.pop_back();
        deq.push_back(i + 1);
    }
    return ans;
}

算法1: 前缀和 + TreeMap

1
2
3
4
5
6
a[0..i] 的和 sums[i + 1] 求出后

由 sum(a[j..i]) = sums[i + 1] - sums[j] <= k
推出 sums[j] >= sums[i + 1] - k

因此问的是 sums[0..i] 中大于等于 sums[i + 1] - k 的最小值是多少

这个提问用单调队列是不好做的，因为 sums[i + 1] - k 这个数一直在变，那队头就一直无法弹出。因为弹出某个 sum 之后，后续在 sums[i + 1] + k 这个限制下，sum 可能又会是答案了。

处理提问 sums[i + 1] 时，sums[0..i] 的信息都是需要的，因此将它们维护在 TreeMap 中以便高效查询。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxSubArray(vector<int>& nums, int k)
{
    int n = nums.size();
    multiset<int> sums;
    sums.insert(0);
    int sum = 0;
    int ans = INT_MIN;
    for(int i = 0; i < n; ++i)
    {
        sum += nums[i];
        // 问: sums 中大于等于 sum - k 的最小值是多少
        auto it = sums.lower_bound(sum - k);
        if(it != sums.end())
            ans = max(ans, sum - *it);
        sums.insert(sum);
    }
    return ans;
}

算法2: 前缀和 + 排序 + 双指针

如果前缀和 sums 已有，则现在要找到最大的不超过 k 的两个前缀和之差，也就是在 sums 上找两个数 sums[i] 和 sums[j] (i < j)，使得 sums[j] - sums[i] 最大且 <= k。

有个类似的但是更简单题目可以参考：求数组中最大的不超过 k 的两个数之和。我们首先看一下这个题：

给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k 。如果没有满足此等式的 i,j 存在，则返回 -1 。

这个求小于 k 两数最大和的问题是力扣上的一个简单题，方法就是先排序再走一轮双向双指针，这个比较好想，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int K) {
        if(A.empty()) return -1;
        int n = A.size();
        if(n == 1) return -1;
        sort(A.begin(), A.end());
        int left = 0, right = n - 1;
        int result = INT_MIN;
        bool flag = false;
        while(left < right)
        {
            int sum = A[left] + A[right];
            if(sum >= K)
                --right;
            else
            {
                result = max(result, sum);
                ++left;
                flag = true;
            }
            if(result == K - 1)
                return K - 1;
        }
        if(flag)
            return result;
        else
            return -1;
    }
};

在上面的求小于 k 两数最大和的问题中，方法就是先排序再走一轮双向双指针。

而在本题中，是求的不超过 k 的两数最大的差，对 sums 排序后需要在上面的算法中做三点改动:

  1. 将双向双指针改为单向双指针。
  2. 单向双指针的过程做两遍，第一遍考察 sums[i] - sums[j] 即考察负的差值，第二遍考察 sums[j] - sums[i] 即考察正的差值。
  3. 对 sums 排序时需要带着 idx 信息。当满足以下条件之一时更新答案:
  • sums[i] - sums[j] <= k 且 sums[i].idx > sums[j].idx
  • sums[j] - sums[i] <= k 且 sums[j].idx > sums[i].idx

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int maxSubArray(vector<int>& nums, int k)
{
    using PII = pair<int, int>;
    vector<PII> sums(nums.size() + 1);
    sums[0] = {0, 0};
    int n = sums.size();
    for(int i = 1; i < n; ++i)
        sums[i] = {sums[i - 1].first + nums[i - 1], i};
    sort(sums.begin(), sums.end());
    int max_diff = INT_MIN;
    // 第一轮: 考察负的差值
    int i = 0, j = 1;
    while(j < n)
    {
        int diff = sums[i].first - sums[j].first;
        // [i..j]
        if(diff <= k)
        {
            if(sums[i].second > sums[j].second)
                max_diff = max(max_diff, diff);
            ++i;
            if(i == j)
                ++j;
        }
        else
            ++j;
    }
    // 第一轮: 考察正的差值
    i = 0, j = 1;
    while(j < n)
    {
        int diff = sums[j].first - sums[i].first;
        if(diff <= k)
        {
            if(sums[j].second > sums[i].second)
                max_diff = max(max_diff, diff);
            ++j;
        }
        else
        {
            ++i;
            if(i == j)
                ++j;
        }
    }
    return max_diff;
}
Share