C++算法:柱状图中最大的矩形

简介: C++算法:柱状图中最大的矩形


题目

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:

输入:heights = [2,1,5,6,2,3]

输出:10

解释:最大的矩形为图中红色区域,面积为 10

示例 2:

输入: heights = [2,4]

输出: 4

分析

可以用单调栈解决。

23年3月

class Solution {
public:
int largestRectangleArea(vector& heights) {
m_c = heights.size();
vector vMaxLeft;
{
vector<std::pair<int, int>> vLeft;
for (int i = 0; i < heights.size(); i++)
{
const int& h = heights[i];
const int iLessNum = std::lower_bound(vLeft.begin(), vLeft.end(), h, [](const std::pair<int, int>& p, const int i)
{
return p.first < i;
}) - vLeft.begin();
if (0 == iLessNum)
{
vMaxLeft.push_back(-1);
}
else
{
vMaxLeft.push_back(vLeft[iLessNum - 1].second);
}
while (vLeft.size() && (vLeft.back().first >= h))
{
vLeft.pop_back();
}
vLeft.emplace_back(h, i);
}
}
int iMax = INT_MIN;
   {
     vector<std::pair<int, int>> vRight;
     for (int i = m_c - 1; i >= 0; i--)
     {
       const int& h = heights[i];
       const int iLessNum = std::lower_bound(vRight.begin(), vRight.end(), h+1, [](const std::pair<int, int>& p, const int i)
       {
         return  p.first < i;
       }) - vRight.begin();
       if (0 == iLessNum)
       {
         iMax =max(iMax, h * (m_c -  vMaxLeft[i]-1));
       }
       else
       {
         const int iRight = vRight[iLessNum - 1].second;
         iMax = max(iMax, h * (iRight - vMaxLeft[i]-1));
       }
       while (vRight.size() && (vRight.back().first >= h))
       {
         vRight.pop_back();
       }
       vRight.emplace_back(h, i);
     }
   }
   return iMax;
 }
 int m_c;

};

23年8月

class Solution {
public:
int largestRectangleArea(vector& heights) {
m_c = heights.size();
vector vLeft(m_c, -1), vRight(m_c, m_c);
stack sta;
for (int i = 0; i < heights.size(); i++)
{
while (sta.size() && (heights[i] <= heights[sta.top()] ))
{
vRight[sta.top()] = i;
sta.pop();
}
if (sta.size())
{
vLeft[i] = sta.top();
}
sta.emplace(i);
}
int iRet = 0;
  for (int i = 0; i < m_c; i++)
  {
    iRet = max(iRet, (vRight[i] - vLeft[i] - 1) * heights[i]);
  }
  return iRet;
}
int m_c;

};

其它

视频课程

如果你觉得复杂,想从简单的算法开始,可以学习我的视频课程。

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

我的其它课程

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

测试环境

win7 VS2019 C++17

相关下载

doc版文档,排版好

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


相关文章
|
11天前
|
搜索推荐 算法 C++
|
11天前
|
存储 算法 Serverless
|
11天前
|
存储 算法 搜索推荐
|
18天前
|
算法 数据中心 C++
基于C++雪花算法工具类Snowflake -来自chatGPT
基于C++雪花算法工具类Snowflake -来自chatGPT
14 1
|
28天前
|
算法 前端开发 Linux
【常用技巧】C++ STL容器操作:6种常用场景算法
STL在Linux C++中使用的非常普遍,掌握并合适的使用各种容器至关重要!
42 10
|
23天前
|
算法 数据处理 C++
C++一分钟之-迭代器与算法
【6月更文挑战第21天】C++ STL的迭代器统一了容器元素访问,分为多种类型,如输入、输出、前向、双向和随机访问。迭代器使用时需留意失效和类型匹配。STL算法如查找、排序、复制要求特定类型的迭代器,注意容器兼容性和返回值处理。适配器和算法组合增强灵活性,但过度使用可能降低代码可读性。掌握迭代器和算法能提升编程效率和代码质量。
28 3
|
11天前
|
机器学习/深度学习 算法 搜索推荐
|
18天前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
17 0
|
20天前
|
算法 前端开发 安全
C++算法模板
C++算法模板
17 0
|
23天前
|
算法 Python
二维矩形件排样算法之最低水平线搜索算法实现
二维矩形件排样算法之最低水平线搜索算法实现
24 0