作者推荐
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
本文涉及的知识点
单调栈
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
参数：
1 <= heights.length <=105
0 <= heights[i] <= 104
分析
时间复杂度😮(n)。
枚举
如何不重复不遗漏的枚举所有子数组，最容易想到的枚举子数组的起点和终点[left,right]。这样的时间复杂度是O(n2)，超时。 可以枚举子数组的最小高度heights[i]，再枚举left[i],right[i]。left[i]的取值范围(x1,i]。x1是从i-1到0，第一个heights[x1]<heights[i]，如果不存在，令x1等于-1。right[i]的取值范围[i,x2)。x2是从i+1,到n-1 第一个heights[x2] <= heights[i]，如果不存在，令x2等于m_c。由于要求最大面积，所以left[i]取最小值，right[i]取最大值。即：矩形最底低在i时，宽度最大的子数组为(left[i],right[i])。
x1是小于,x2是小于等于的含义是：如果有多个最低处，以最右边的为准。
符合以下三个条件：
| 两个子状态都有序 |
| 新增的数据有序 |
| 查询有序 |
vLeftHeightIndex
vLeftHeightIndex记录下标和高度。如果i1 < i2，且heights[i1] >= heights[i2]，则i1被淘汰了。淘汰后，下标升序，高度也升序。新增加的数据下标也是按升序加入,这是可以优化成单调栈（向量）的条件。
vLeftHeightIndex.back() 被淘汰，说明heights[i]小于等于vLeftHeightIndex.back()，而且是第一个小于等于的高度。也就是vRight。
代码，
核心代码
class Solution { public: 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; };
测试用例
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<int> heights; int r; { Solution slu; heights = { 2, 1, 5, 6, 2, 3 }; auto res = slu.largestRectangleArea(heights); Assert(10, res); } { Solution slu; heights = { 2,4 }; auto res = slu.largestRectangleArea(heights); Assert(4, res); } }
2023年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; };
2023年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; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
