您现在的位置是：首页 >学无止境 >【leetcode热题100】接雨水、直方图最大矩形面积、矩阵中最大的矩形网站首页学无止境

【leetcode热题100】接雨水、直方图最大矩形面积、矩阵中最大的矩形

命由己造～ 2024-06-04 00:00:03
简介【leetcode热题100】接雨水、直方图最大矩形面积、矩阵中最大的矩形

文章目录

一、接雨水

题目链接

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

在这里插入图片描述

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

方法一：按列求（动态规划）

我们把每一列能接的水加起来即可，而每一列的水只取决于当前列左边的最高墙和右边的最高墙。
根据木桶效应，在左边和右边取低的那一个，然后减去当前列的高度即可求出当前列的接水量。
这样我们就可以创建两个数组，一个记录包括当前列左边的最高墙，一个记录包括当前列右边的最高墙，采用动态规划的思想。
为什么要包括当前列？

首先可以解决边界问题，其次如果当前列是左边最高的或者右边最高的，那么减去自己的高度就是0。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftMax(n), rightMax(n);
        int Max = 0;
        for(int i = 0; i < n; i++)
        {
            if(height[i] > Max)
            {
                Max = height[i];
            }
            leftMax[i] = Max;
        }
        Max = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            if(height[i] > Max)
            {
                Max = height[i];
            }
            rightMax[i] = Max;
        }
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            sum += min(leftMax[i], rightMax[i]) - height[i];
        }
        return sum;
    }
};

方法二：双指针

上面我们说过只用看左右两边最高墙中的最小值即可，所以现在我们定义两个指针，left从左向右，right从右向左，每次让小的那一列墙的指针向中间移动（因为我们不关心左边最高墙和右边最高墙中的高的那列墙）。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int leftMax = 0, rightMax = 0;
        int left = 0, right = n - 1;
        int sum = 0;
        while(left <= right)
        {
            if(height[left] < height[right])
            {
                leftMax = max(leftMax, height[left]);
                sum += leftMax - height[left];
                left++;
            }
            else
            {
                rightMax = max(rightMax, height[right]);
                sum += rightMax - height[right];
                right--;
            }
        }
        return sum;
    }
};

方法三：单调栈

用一个极端场景来举例子：
在这里插入图片描述
如果是单调递减的就依次入栈，直到碰到比栈顶元素要高的墙，此时就依次判断前面入栈且比当前墙要低的元素。

比方说现在到5下标。此时依次出栈之前的元素来计算接水量：
在这里插入图片描述

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> st;
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            while(!st.empty() && height[i] > height[st.top()])
            {
                int cur = st.top();
                st.pop();
                if(st.empty())
                {
                    break;
                }
                int len = i - st.top() - 1;
                sum += (min(height[st.top()], height[i]) - height[cur]) * len;
            }
            st.push(i);
        }
        return sum;
    }
};

二、直方图最大矩形面积

题目链接

题目描述：

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
在这里插入图片描述

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：
在这里插入图片描述

输入： heights = [2,4]
输出： 4

思路分析：

单调栈

这道题可以类比上面的接雨水问题，我们也可以用单调栈的方式来求解。
栈里面存的是下标，主要是用来计算宽度。
遍历每个下标，如果当前列大于栈顶元素，就继续入栈，如果小于栈顶元素，进行处理：
在这里插入图片描述
从1开始遍历，当遍历到1的位置时还不能确定1位置是不是最大的矩形面积，继续向后遍历，当遍历到2的位置时，就可以确定2之前的的大面积了。
在这里插入图片描述
如果已经确定了一个柱形的高度，我们可以无视它（出栈）。
在这里插入图片描述
为什么可以无视呢？
后边的元素一定比1要小，所以当要求最大面积的时候一定会跨过第一列：
在这里插入图片描述
就算1前面也有元素也是可以可以直接跨过。
可以看到2不用关注1，3不用关注1和2。

这里还有两个特殊的情况：
1️⃣ 弹栈的时候，栈为空；
2️⃣ 遍历完成以后，栈中还有元素；

如果弹栈的时候栈为空，那么说明宽度要从当前位置一直延伸到0下标。
如果遍历完后栈中还有元素。比如说这个图：
在这里插入图片描述
最后剩下的就是4和6，对于4和6，先处理6在处理4：
在这里插入图片描述

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;
        int ans = 0;
        for(int i = 0; i < n; i++)
        {
            while(!st.empty() && heights[i] < heights[st.top()])
            {
                int mid = st.top();
                st.pop();
                int w = i;
                if(!st.empty())
                {
                    w = i - st.top() - 1;
                }
                ans = max(ans, w * heights[mid]);
            }
            st.push(i);
        }
        while(!st.empty())
        {
            int mid = st.top();
            st.pop();
            int w = n;
            if(!st.empty())
            {
                w = n - st.top() - 1;
            }
            ans = max(ans, w * heights[mid]);
            cout << w * heights[mid] << endl;
        }
        return ans;
    }
};

哨兵位优化

为了处理上面两个特殊情况，我们可以在首位都添加一个0。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int n = heights.size();
        stack<int> st;
        st.push(0);
        int ans = 0;
        for(int i = 1; i < n; i++)
        {
            while(heights[i] < heights[st.top()])
            {
                int mid = st.top();
                st.pop();
                int left = st.top();
                int right = i;
                int w = right - left - 1;
                ans = max(ans, w * heights[mid]);
            }
            st.push(i);
        }
        return ans;
    }
};

三、矩阵中最大的矩形

题目链接

题目描述：

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。
注意：此题 matrix 输入格式为一维 01 字符串数组。

示例 1：
在这里插入图片描述

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

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [“0”]
输出：0

示例 4：

输入：matrix = [“1”]
输出：1

示例 5：

输入：matrix = [“00”]
输出：0

思路分析：
例如上面的图，我们可以分层看，每一层都是求直方图最大矩形面积。

第一层柱状图的高度[“1”,“0”,“1”,“0”,“0”]，最大面积为1；
第二层柱状图的高度[“2”,“0”,“2”,“1”,“1”]，最大面积为3；
第三层柱状图的高度[“3”,“1”,“3”,“2”,“2”]，最大面积为6；
第四层柱状图的高度[“4”,“0”,“0”,“3”,“0”]，最大面积为4；

这道题的解法就是前缀和+单调栈

前缀和+单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;
        st.push(0);
        int ans = 0;
        for(int i = 1; i < n; i++)
        {
            while(heights[i] < heights[st.top()])
            {
                int mid = st.top();
                st.pop();
                int left = st.top();
                int right = i;
                int w = right - left - 1;
                ans = max(ans, w * heights[mid]);
            }
            st.push(i);
        }
        return ans;
    }

    int maximalRectangle(vector<string>& matrix) {
        if(matrix.size() == 0) return 0;
        int res = 0;
        vector<int> v(matrix[0].size() + 2);
        for(int i = 0; i < matrix.size(); i++)
        {
            for(int j = 0; j < matrix[i].size(); j++)
            {
                if(matrix[i][j] == '1')
                {
                    v[j + 1] += 1;
                }
                else
                {
                    v[j + 1] = 0;
                }
            }
            res = max(res, largestRectangleArea(v));
        }
        return res;
    }
};
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐