Day 60 单调栈
84. 柱状图中最大的矩形
暴力解法
超时了
分别找出当前位置左边第一个比自己小的索引(的后一个位置)和右边第一个比自己小的索引(的前一个位置),这个范围之内,就是以当前位置的高度所能达到的最大宽度。文章来源:https://www.toymoban.com/news/detail-633452.html
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxArea = 0;
for (int i = 0; i < heights.size(); ++i)
{
int leftLowerIdx = i, rightLowerIdx = i;
for (int j = i; j >= 0; --j)
{
if (heights[j] < heights[i])
{
break;
}
else
{
leftLowerIdx = j;
}
}
for (int j = i; j < heights.size(); ++j)
{
if (heights[j] < heights[i])
{
break;
}
else
{
rightLowerIdx = j;
}
}
int area = heights[i] * (rightLowerIdx - leftLowerIdx + 1);
if (area > maxArea)
{
maxArea = area;
}
}
return maxArea;
}
};
双指针
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> leftLower(heights.size(), 0);
leftLower[0] = -1; // 注意这个地方是 - 1,否则会导致死循环
for (int i = 1; i < heights.size(); ++i)
{
int t = i - 1;
while (t >= 0 && heights[t] >= heights[i])
{
t = leftLower[t];
}
leftLower[i] = t;
}
vector<int> rightLower(heights.size(), 0);
rightLower.back() = heights.size(); // 注意这个地方的值为heights.size(),否则会导致死循环
for (int i = heights.size() - 2; i >= 0; --i)
{
int t = i + 1;
while (t < heights.size() && heights[t] >= heights[i])
{
t = rightLower[t];
}
rightLower[i] = t;
}
int maxArea = 0;
for (int i = 0; i < heights.size(); i++)
{
int area = heights[i] * (rightLower[i] - leftLower[i] - 1);
if (area > maxArea)
{
maxArea = area;
}
}
return maxArea;
}
};
单调栈
有了接雨水那道题的经验,这一道题可以模仿着做出了文章来源地址https://www.toymoban.com/news/detail-633452.html
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxArea = 0;
stack<int> incStk;
incStk.push(-1);
heights.push_back(-1);
for (int i = 0; i < heights.size(); ++i)
{
while (incStk.top() != -1 && heights[incStk.top()] > heights[i])
{
int idx = incStk.top();
incStk.pop();
int w = i - incStk.top() - 1;
int area = heights[idx] * w;
if (area > maxArea)
{
maxArea = area;
}
}
incStk.push(i);
}
return maxArea;
}
};
到了这里,关于算法刷题Day 60 柱状图中的最大矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!