算法基础算法

二维转一维

字数统计: 1.3k字   |   阅读时长: 5分
, ,

摘要: 基于一维问题的解法，解决二维问题

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

一维数组上有一些常见的问题，应用了正确的算法后可以很好地解决。这些问题经常在二维矩阵上也有类似的问题。比如一维数组上求区间相关指标的问题，在二维上就是求矩阵相关指标的问题。

对于二维矩阵上的问题，有的是需要用矩阵上特有的算法，比如棋盘 DP；但也有很多是可以先枚举每一行或每一列，再解决同一行或同一列的一维数组上的问题。

本文我们首先利用二维转一维的思想，解决 01 矩阵中的最大矩形问题，过程就是先转化为直方图中最大矩形问题，然后调用该问题的单调栈解法。

之后再看几组类似的问题。将二维问题转化为一维问题，然后调用一维问题解法。每一组问题，我们先给出一维问题并解决，然后看二维问题并通过拆解成一维问题并套用已有的一维问题的方法解决。

第一组: 01矩阵中的最大矩形

一维问题：84. 柱状图中最大的矩形

一维问题的算法是单调栈，参考文章 单调栈

二维问题：85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

提示：

1
2
3
4
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

示例 1：

输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出：6
解释：最大矩形如上图所示。

示例 2：
输入：matrix = []
输出：0

示例 3：
输入：matrix = [[“0”]]
输出：0

示例 4：
输入：matrix = [[“1”]]
输出：1

示例 5：
输入：matrix = [[“0”,”0”]]
输出：0

算法：单调栈

$M \times N$ 的矩阵，一行一行地考虑，对于第 $i$ 行，矩阵的第 0 到第 $i$ 行可以视为一个直方图，然后照搬一维问题的做法求该直方图上的最大矩形。一共有 $M$ 个直方图，总时间复杂度 $O(MN)$。下面是示意图：

代码 (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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<int> heights(m, 0);
        int result = 0;
        for(int i = 0; i < n; ++i)
        {
            _get_geights(matrix, heights, i);
            int result_i = _max_rec_hist(heights);
            result = max(result, result_i);
        }
        return result;
    }

private:
    void _get_geights(vector<vector<char> >& matrix, vector<int>& heights, int i)
    {
        int m = matrix[0].size();
        for(int j = 0; j < m; ++j)
        {
            int cnt = 0;
            int h = i;
            while(h >= 0 && matrix[h][j] == '1')
            {
                ++cnt;
                --h;
            }
            heights[j] = cnt;
        }
    }

    int _max_rec_hist(vector<int>& heights)
    {
        int m = heights.size();
        stack<int> st;
        st.push(-1);
        int result = 0;
        for(int j = 0; j < m; ++j)
        {
            while(st.top() != -1 && heights[st.top()] > heights[j])
            {
                int h = heights[st.top()];
                st.pop();
                int l = st.top();
                int w = j - l - 1;
                result = max(result, h * w);
            }
            st.push(j);
        }
        while(st.top() != -1)
        {
            int h = heights[st.top()];
            st.pop();
            int l = st.top();
            int w = m - l - 1;
            result = max(result, w * h);
        }
        return result;
    }
};

第二组: 整数矩阵的最大子矩阵和

一维问题: 53. 最大子数组和

一维问题的解法为动态规划，参考文章 最大子数组和。

二维问题: 面试题 17.24. 最大子矩阵

二维问题及其解答参考文章 最大子矩阵和。

第三组: 带大小限制最大子矩阵和

一维问题: 带长度限制的最大子数组和

一维问题解法是单调队列。参考文章 单调队列。

二维问题: 363. 矩形区域不超过 K 的最大数值和

一维问题和二维问题的解答，参考文章 带大小限制的最大子数组/子矩阵和。

第四组: 滑动矩形最大值

一维问题: 239. 滑动窗口最大值

一维问题是定长滑动窗口最大值，算法为单调队列，参考文章 力扣239-滑动窗口最大值。

二维问题：二维的滑动窗口最大值

二维问题的算法与代码参考文章 二维的滑动窗口最大值。

第五组: 和为目标值的子矩阵数量

一维问题: 560. 和为K的子数组

一维问题的解法为用哈希映射维护前缀和，参考文章 在数据结构中维护前缀和：区间(矩形/路径)和等于(大于)目标值。

二维问题: 1074. 元素和为目标值的子矩阵数量

二维问题的算法与代码参考文章 力扣1074-元素和为目标值的子矩阵数量。

Share