直方图系列 | lostfly's blog

文章目录

1. 直方图中最大的矩阵
2. 雨水积存问题
3. 矩阵中全是1的最大子矩阵

LeetCode上有一系列有关直方图的题目。

这些题目我本来都是不会做的，在网上查阅到第一题的做法之后，我发现他们都可以用同一种做法。

直方图中最大的矩阵

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

直方图示意

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

直方图中的矩阵示意
The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

这个问题的难点在于我们不知道怎么样去遍历所有的直方图中的矩阵，然后找到面积最大的那个。

我一开始的想法是矩阵都是有一个开头的，以每个柱体作为矩阵的开头去寻找最大的矩阵，逻辑是正确的，但是遍历的时间复杂度太高，是O(n^2)，直观的感觉这种题目，时间复杂度应该是O(n)的。

我找到的方法里，它的遍历方法是找到以某个柱体为最低高度的面积最大的矩阵。比如上图里红色的矩阵是以3号柱体为最低高度的，三号柱体决定了矩阵的高度。

那如何找到以某个柱体为最低高度的矩阵呢？对某个柱体来说，往左边找到比他矮的第一个柱体，往右边找到第一个比他矮的柱体，左右两个柱体中间的矩形就是以某个柱体为最低高度的矩形了。因为这个矩形再往左走，或者右走，都不是以这个柱体作为最低高度的了。

现在问题的关键就转换到如何找到某个柱体左边，和右边比他矮的第一个柱体了。这里使用栈，可以巧妙的实现这一功能，我们建立一个栈，栈中记录的是各个柱体的坐标，栈里存放的柱体高度是非递减的。

我们从左到右扫描直方图，当栈为空或者新的柱体高度不比栈顶的柱体高度矮的时候就将其推入栈，否则这个柱体就是栈顶柱体的右边第一个比他矮的柱体，而栈顶柱体的前一个柱体就是柱体左边第一个比他矮的柱体，因为栈里面的柱体存放是非递减的。这样，我们就可以直接计算以栈顶柱体为最低高度的矩阵面积了。

int bar_index = s.top();
s.pop();
int area = height[bar_index] * (s.empty() ? index : index - s.top() - 1);

上面是计算矩阵面积的代码，index表示的是当前遍历到的柱体的坐标，是栈顶柱体的右边第一个比它矮的柱体的坐标。

在计算矩阵面积的时候有两种情况，一种是弹出栈顶柱体后，栈里已经没有元素了，说明在栈顶柱体的左边没有比他矮的柱体，另外一种情况就是栈里还有元素，矩阵的左右边界就是栈顶柱体坐标到遍历到的柱体坐标了。

下面是全部实现代码。

int largestRectangleArea(vector<int> &height)
{
    stack<int> s;
    int len = height.size();
    if (len == 0)
        return 0;
    int index = 0;
    int max_area = 0;
    while (index < len)
    {
        if (s.empty() || height[index] >= height[s.top()])
        {
            s.push(index++);
        }
        else
        {
            int bar_index = s.top();
            s.pop();
            int area = height[bar_index] * (s.empty() ? index : index - s.top() - 1);
            if (area > max_area)
                max_area = area;
        }
    }
    while (!s.empty())
    {
        int bar_index = s.top();
        s.pop();
        int area = height[bar_index] * (s.empty() ? index : index - s.top() - 1);
        if (area > max_area)
            max_area = area;
    }
    return max_area;
}

雨水积存问题

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

雨水积存问题示意

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

这道题同样是直方图的形式，问的是直方图中可以存储多少雨水。和上一道题一样，关键在于如何计算雨水的体积（面积）。

我们可以采用和上一道题相似的定义方法。我们计算以某一个柱体为最低高度的区间大小，对于某一个柱体来说，往左边找第一个比他高的柱体，往右边找第一个比他高的柱体，那左右两个柱体围出的区域就是以这个柱体为最低高度的存储雨水区间。
这里有一些地方值得注意：

对于某一个柱体来说，两边不一定都有比他高的柱体，这说明并没有以他为最低高度的存储雨水区域

对于整块连成一片的储水区域，我们并不是一起计算的，是分层次计算的。

这里同样用栈作为核心的数据结构。我们建立一个栈，里面存放了柱体的坐标，栈里的柱体是递减存放的。
我们从左到右顺序扫描柱体，如果柱体的高度比栈顶的柱体小，就压入栈，否者我们可以计算以栈顶柱体为最低高度的储水区域。

bar_index = s.top();
s.pop();
if (s.empty())
    continue;
if (A[s.top()] > A[index])
    rain = (A[index] - A[bar_index]) * (index - s.top() - 1);
else
    rain = (A[s.top()] - A[bar_index]) * (index - s.top() - 1);
total += rain;

这里计算储水区域的时候，是以左右柱体高度中较低者与栈顶柱体之间的高度差作为储水区域的高度，长度是左右两边柱体的距离。另外，因为栈里的柱体高度是递减存放的，所以可能会存在处理和栈顶柱体同样高度的柱体的情况，这时候，因为计算出来的高度差是0，储水区域也为0，并不会重复计算储水区域。

下面是这道题的全部实现代码：

int trap(int A[], int n)
{
    if (n <= 1)
        return 0;
    stack<int> s;
    int index = 0;
    int total = 0;
    int rain;
    int bar_index;
    while (index < n)
    {
        if (s.empty() || A[index] < A[s.top()])
        {
            s.push(index++);
        }
        else
        {
            bar_index = s.top();
            s.pop();
            if (s.empty())
                continue;
            if (A[s.top()] > A[index])
                rain = (A[index] - A[bar_index]) * (index - s.top() - 1);
            else
                rain = (A[s.top()] - A[bar_index]) * (index - s.top() - 1);
            total += rain;
        }
    }
    return total;
}

矩阵中全是1的最大子矩阵

Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

题目的描述非常简单，可能会产生歧义，我第一次做的时候就完全把题目想歪了，把题目想成是找到一个子矩阵，里面的包含了原矩阵中所有的1。其实题目的意思是在原有的元素是0和1的矩阵里面找到一个最大的子矩阵，这个子矩阵里全是1。

仔细想想，这题同样是一个直方图的问题，我们把矩阵中连续是1的区间想象成是柱体就可以了。

理论上这个矩阵中的直方图是正的，或者是倒的都可以，不过在我的直接想象中，这个直方图是歪着的，顺时针旋转了90度。

矩阵形态转换

首先我们要将矩阵中的直方图标注出来，并且标明柱体的高度，这部分可以用动态规划来做，把原来矩阵中为1的元素改成以改元素为起点的连续1的个数。

vector<vector<int>> continuous_ones(m, vector<int>(n));
for (int row = 0; row < m; row++) {
    if (matrix[row][n - 1] == '1')
        continuous_ones[row][n - 1] = 1;
    for (int col = n - 2; col >= 0; col--) {
        if (matrix[row][col] == '1')
            continuous_ones[row][col] = continuous_ones[row][col + 1] + 1;
    }
}

然后对每一列，都做直方图中最大的矩阵计算就可以了。

下面是本题的全部实现代码：

int maximalRectangle(vector<vector<char> > &matrix) {
    int m = matrix.size();
    if (m == 0)
        return 0;
    int n = matrix.front().size();
    vector<vector<int>> continuous_ones(m, vector<int>(n));
    for (int row = 0; row < m; row++) {
        if (matrix[row][n - 1] == '1')
            continuous_ones[row][n - 1] = 1;
        for (int col = n - 2; col >= 0; col--) {
            if (matrix[row][col] == '1')
                continuous_ones[row][col] = continuous_ones[row][col + 1] + 1;
        }
    }
    int max_area = 0;
    for (int col = 0; col < n; col++)
    {
        stack<int> s;
        int row = 0;
        while (row < m)
        {
            if (s.empty() || continuous_ones[row][col] > continuous_ones[s.top()][col])
            {
                s.push(row++);
            }
            else
            {
                int height = continuous_ones[s.top()][col];
                s.pop();
                int area = height * (s.empty() ? row : (row - s.top() - 1));
                if (area > max_area)
                    max_area = area;
            }
        }
        while (!s.empty())
        {
            int row_index = s.top();
            s.pop();
            int area = continuous_ones[row_index][col] *
                (s.empty() ? row : (row - s.top() - 1));
            if (area > max_area)
                max_area = area;
        }
    }
    return max_area;
}