【单调栈】【区间合并】LeetCode85:最大矩形

简介: 【单调栈】【区间合并】LeetCode85:最大矩形

题目

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 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”]]

输出:0

示例 3:

输入:matrix = [[“1”]]

输出:1

参数范围

rows == matrix.length

cols == matrix[0].length

1 <= row, cols <= 200

matrix[i][j] 为 ‘0’ 或 ‘1’

分析

时间复杂度O(n2m)。枚举矩形的left和right,时间复杂度o(n^2)。指定left,right,计算连续1的数量大于等于width的行数,时间复杂度O(m)。

代码

核心代码

class Solution {
public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    m_r = matrix.size();
    m_c = matrix.front().size();
    vector<vector<int>> vRightLen(m_r, vector<int>(m_c));
    for (int r = 0; r < m_r; r++)
    {
      for (int c = m_c - 1; c >= 0; c--)
      {
        if ('1' == matrix[r][c])
        {
          vRightLen[r][c] = 1 + ((m_c - 1 == c) ? 0 : vRightLen[r][c + 1]);
        }
      }
    }
    int iRet = 0;
    for (int left = 0; left < m_c; left++)
    {
      for (int right = left; right < m_c; right++)
      {
        const int width = right - left + 1;
        int height = 0;
        for (int r = 0; r < m_r; r++)
        {
          if (vRightLen[r][left] < width)
          {
            iRet = max(iRet, height * width);
            height = 0;
          }
          else
          {
            height++;
          }
        }
        iRet = max(iRet, height * width);
      }
    }
    return iRet;
  }
  int m_r, m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<vector<char>> matrix;
  int r;
  {
    Solution slu;   
    matrix = { {'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'} };
    auto res = slu.maximalRectangle(matrix);
    Assert(6, res);
  }
  {
    Solution slu;
    matrix = { {'0'} };
    auto res = slu.maximalRectangle(matrix);
    Assert(0, res);
  }
  {
    Solution slu;
    matrix = { {'1'} };
    auto res = slu.maximalRectangle(matrix);
    Assert(1, res);
  }
  {
    Solution slu;
    matrix = { {'1','1'}};
    auto res = slu.maximalRectangle(matrix);
    Assert(2, res);
  }
  {
    Solution slu;
    matrix = { {'1'},{'1' } };
    auto res = slu.maximalRectangle(matrix);
    Assert(2, res);
  }
}

单调栈

枚举底部,本题就可以转化成柱形图的最大矩形

class Solution {
public:
  int maximalRectangle(vector<vector<char>>& matrix) {    
    m_c = matrix.front().size();
    vector<int> vHeights(m_c);
    int iRet = 0;
    for (int r = 0; r < matrix.size(); r++)
    {
      for (int c = m_c - 1; c >= 0; c--)
      {
        if ('1' == matrix[r][c])
        {
          vHeights[c] +=1 ;
        }
        else
        {
          vHeights[c] = 0 ;
        }
      }
      iRet = max(iRet, largestRectangleArea(vHeights));
    }
    return iRet;
  }
  int largestRectangleArea(vector<int>& heights) {
    m_c = heights.size();
    vector<pair<int, int>> vLeftHeightIndex;
    vector<int> vLeftFirstLess(m_c, -1), vRightFirstMoreEqual(m_c, m_c);//别忘记初始化
    for (int i = 0; i < m_c; i++)
    {
      while (vLeftHeightIndex.size() && (heights[i] <= vLeftHeightIndex.back().first))
      {
        vRightFirstMoreEqual[vLeftHeightIndex.back().second] = i;
        vLeftHeightIndex.pop_back();
      }
      if (vLeftHeightIndex.size())
      {
        vLeftFirstLess[i] = vLeftHeightIndex.back().second;
      }
      vLeftHeightIndex.emplace_back(heights[i], i);
    }
    int iRet = 0;
    for (int i = 0; i < m_c; i++)
    {
      iRet = max(iRet, heights[i] * (vRightFirstMoreEqual[i] - vLeftFirstLess[i] - 1));
    }
    return iRet;
  }
  int m_c;
};

2022年12月版代码

class Solution {
 public:
   int maximalRectangle(vector<vector<char>>& matrix) {
     m_r = matrix.size();
     m_c = matrix[0].size();
     vector<vector<int>> leftNums;
     leftNums.assign(m_r, vector<int>(m_c));
     for (int r = 0; r < m_r; r++)
     {
       for (int c = 0; c < m_c; c++)
       {
         if ('0' == matrix[r][c])
         {
           leftNums[r][c] = 0;
         }
         else
         {
           leftNums[r][c] = 1 + ((c > 0) ? leftNums[r][c - 1] : 0);
         }
       }
     }
     for (int c = 0; c < m_c; c++)
     {
       stack<pair<int, int>> sta;      
       for (int r = 0; r < m_r; r++)
       {
         int iMinR = r;
         while (sta.size() && (sta.top().first > leftNums[r][c]))
         {
           PopStack(sta, iMinR, r);
         }
         if (sta.empty() || (sta.top().first < leftNums[r][c]))
         {
           sta.emplace(leftNums[r][c], iMinR);
         }
       }
       while (sta.size())
       {
         int iMinR = m_r;
         PopStack(sta, iMinR, m_r);
       }
     }
     return m_iMaxArea;
   }
   void PopStack(stack<pair<int, int>>& sta,int& iMinRow,int r )
   {
     int iWidth = sta.top().first;
     iMinRow = sta.top().second;
     sta.pop();
     m_iMaxArea = max(m_iMaxArea, iWidth*(r - 1 - iMinRow + 1));
   }
   int m_r, m_c;
   int m_iMaxArea = 0;
 };


扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

| 我想对大家说的话 ||-|

|闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。|

| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |

|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法用**C++**实现。



目录
打赏
0
0
0
0
36
分享
相关文章
力扣经典150题第五十四题:最小栈
力扣经典150题第五十四题:最小栈
46 0
|
3月前
|
Leetcode第57题(插入区间)
LeetCode第57题“插入区间”的解题方法,包括题目描述、示例、算法思路和代码实现,旨在解决将新区间插入有序且不重叠的区间列表中,并合并重叠区间的问题。
27 0
Leetcode第57题(插入区间)
|
3月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
19 0
|
3月前
|
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
26 0
LeetCode第57题插入区间
LeetCode第57题"插入区间"的解题方法,利用原区间集有序的特性,通过三步插入操作,有效实现了新区间的插入和重叠区间的合并。
LeetCode第57题插入区间
|
5月前
|
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案,通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
37 6
|
5月前
|
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
36 4
|
5月前
|
【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
使用两个栈实现队列的Python解决方案,包括初始化两个栈、实现在队列尾部添加整数的appendTail方法和在队列头部删除整数的deleteHead方法,以及相应的示例操作。
42 2
|
5月前
|
【Leetcode刷题Python】232. 用栈实现队列
如何使用Python语言通过两个栈来实现队列的所有基本操作,包括入队(push)、出队(pop)、查看队首元素(peek)和判断队列是否为空(empty),并提供了相应的代码实现。
25 0
|
6月前
|
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等