【单调栈】【网格】【柱图面积】85. 最大矩形-阿里云开发者社区

【单调栈】【网格】【柱图面积】85. 最大矩形

2024-04-10 25

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【单调栈】【网格】【柱图面积】85. 最大矩形

作者推荐

视频算法专题

本文涉及的基础知识点

单调栈分类、封装和总结

网格

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’

单调栈

求以各行为底的柱状图的最大矩形面积。

vHeight 是柱形图的高度

for (int c = 0; c < m_c; c++)
{
if ((‘0’ == matrix[r][c]))
{
vHeight[c] = 0;
}
else
{
vHeight[c]++;
}
}

MaxArea 求柱形图最大矩形面积。

枚举以 vHeight[i]为高度的矩形，此矩形的左边界为：从右向左，第一个小于等于vHeight[i]的柱子。

此矩形的右边界为，从左到右，第一个小于vHeight[i]的柱子。

左开右开空间。

代码

核心代码

template
class CRangFeture
{
public:
CRangFeture(const vector& nums) :m_nums(nums), Que(m_queIndexs)
{

}
int AddIndex(int cur)
{
  while (m_queIndexs.size() && (m_pr(m_nums[cur], m_nums[m_queIndexs.back()])))
  {
    m_queIndexs.pop_back();
  }
  int iRet = (m_queIndexs.size()) ? m_queIndexs.back() : -1;
  m_queIndexs.push_back(cur);
  return iRet;
}
void RemoveHeadIndex(int cur)
{
  if (m_queIndexs.size() && (cur == m_queIndexs.front()))
  {
    m_queIndexs.pop_front();
  }
}
const deque<int>& Que;

protected:
int FrontValue()
{
return m_nums[m_queIndexs.front()];
}
deque m_queIndexs;
const vector& m_nums;
_PrCurValueCmpTailValue m_pr;
};
class Solution {
public:
int maximalRectangle(vector<vector>& matrix) {
m_c = matrix[0].size();
vector vHeight(m_c);
int iRet = 0;
for (int r = 0; r < matrix.size(); r++)
{
for (int c = 0; c < m_c; c++)
{
if ((‘0’ == matrix[r][c]))
{
vHeight[c] = 0;
}
else
{
vHeight[c]++;
}
}
iRet = max(iRet, MaxArea(vHeight));
}
return iRet;
}
int MaxArea(const vector& vHeight)
{
vector vLeft(m_c,-1);
CRangFeture<std::less> rLeft(vHeight);
for (int i = 0; i < m_c; i++)
{
vLeft[i] = rLeft.AddIndex(i);
}
int iRet = 0;
vector revNums(vHeight.rbegin(), vHeight.rend());
CRangFeture<std::less_equal> rRight(revNums);
for (int i = 0; i < m_c; i++)
{
const int iRight = m_c-1- rRight.AddIndex(i);
const int leftIndex = m_c - 1 - i;
const int iArea = (iRight - vLeft[leftIndex] - 1) * vHeight[leftIndex];
iRet = max(iRet, iArea);
}
return iRet;
}
int m_c;
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
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]);
  }
}
int main()
{
  vector<vector<char>> matrix;
  {
    Solution sln;
    matrix = { {'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'} };
    auto res = sln.maximalRectangle(matrix);
    Assert(6, res);
  }
  {
    Solution sln;
    matrix = { {'0'} };
    auto res = sln.maximalRectangle(matrix);
    Assert(0, res);
  }
  {
    Solution sln;
    matrix = { {'1'} };
    auto res = sln.maximalRectangle(matrix);
    Assert(1, res);
  }
}

优化单调栈

当cur被淘汰pre时，说明cur < pre，且cur 是第一个小于pre的，否则pre会第一个cur淘汰。

故：vRight[pre] =cur

template<class _PrCurValueCmpTailValue>
class CRangFeture
{
public:
  CRangFeture(const vector<int>& nums) :m_nums(nums), Que(m_queIndexs)
  {
  }
  int AddIndex(int cur)
  {
    while (m_queIndexs.size() && (m_pr(m_nums[cur], m_nums[m_queIndexs.back()])))
    {
      OnPop(cur, m_queIndexs.back());
      m_queIndexs.pop_back();
    }
    int iRet = (m_queIndexs.size()) ? m_queIndexs.back() : -1;
    m_queIndexs.push_back(cur);
    return iRet;
  }
  void RemoveHeadIndex(int cur)
  {
    if (m_queIndexs.size() && (cur == m_queIndexs.front()))
    {
      m_queIndexs.pop_front();
    }
  }
  const deque<int>& Que;
protected:
  virtual void OnPop(int cur, int pre) {};
  int FrontValue()
  {
    return m_nums[m_queIndexs.front()];
  }
  deque<int> m_queIndexs;
  const vector<int>& m_nums;
  _PrCurValueCmpTailValue m_pr;
};
template<class _PrCurValueCmpTailValue>
class CLeftRight : public CRangFeture<_PrCurValueCmpTailValue>
{
public:
  CLeftRight(const vector<int>& nums) :CRangFeture<_PrCurValueCmpTailValue>(nums)
  {
    m_vLeft.assign(nums.size(), -1);
    m_vRight.assign(nums.size(), nums.size());
  }
  void Init()
  {
    for (int i = 0; i < this->m_nums.size(); i++)
    {
      m_vLeft[i] = this->AddIndex(i);
    }
  }
  vector<int> m_vLeft, m_vRight;
protected:
  void OnPop(int cur, int pre)
  {
    m_vRight[pre] = cur;
  }
};
class Solution {
public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    m_c = matrix[0].size();
    vector<int> vHeight(m_c);
    int iRet = 0;
    for (int r = 0; r < matrix.size(); r++)
    {
      for (int c = 0; c < m_c; c++)
      {
        if (('0' == matrix[r][c]))
        {
          vHeight[c] = 0;
        }
        else
        {
          vHeight[c]++;
        }
      }
      iRet = max(iRet, MaxArea(vHeight));
    }
    return iRet;
  }
  int MaxArea(const vector<int>& vHeight)
  {   
    CLeftRight<std::less<int>> lr(vHeight); 
    lr.Init();
    int iRet = 0;   
    for (int i = 0; i < m_c; i++)
    {
      const int iArea = (lr.m_vRight[i] - lr.m_vLeft[i] - 1) * vHeight[i];
      iRet = max(iRet, iArea);
    }
    return iRet;
  }
  int m_c;
};

扩展阅读

视频课程

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

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

如何你想快

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

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

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

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

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