题目
给定 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
