84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=10(5)
0 <= heights[i] <= 10(4)
1.
思路就是以每一个位置的柱状图的高度作为矩形的高,然后看以这个高能够扩多长的底,计算这个情况下的面积.
问题被划分为几个小的部分,以每一个高度为高去计算.
2.
单调栈存储左小于,右小于.
老旧的单调栈写法是在元素出栈的时候维护数据.
但是发现这样特别浪费内存,有的时候还需要给栈开辟二维空间处理相同的数据.
这种做法实在是太低效了,并且在这道题目的提交结果居然超出了题目的内存.
3.
全新的版本,只用一个单独的栈就可以完成重复元素或者不重复元素.
首先我们需要确定我们的目的是什么,是填写信息每一个元素左小于,右小于的信息.
老旧版本是在出栈的时候维护信息,全新版本是在入栈的时候维护信息.
每一个元素入栈的时候,维护栈内单调性,然后维护入栈元素左小于或者右小于信息.
对于每一个入栈元素,栈内一定是单调性,此时一定可以找到左小于或者右小于.
老旧版本
class Solution {
public:
vector<int> arr;
int n;
int ret;
using p = pair<int, int>;
vector<p> p_m;
vector<vector<int>> st;
void init() {
n = arr.size();
p_m.clear(), p_m.resize(n);
}
void solve() {
int i = 0;
while (1) {
if (i >= n)
break;
if (st.empty())
st.push_back({i});
else {
auto top = st.back();
while (1) {
if (arr[i] >= arr[top[0]])
break;
st.pop_back();
for (auto& x : top) {
p_m[x].second = i;
p_m[x].first = st.empty() ? -1 : st.back().back();
}
if (st.empty())
break;
else
top = st.back();
}
if (st.empty())
st.push_back({i});
else {
if (arr[st.back()[0]] == arr[i])
st.back().push_back(i);
else
st.push_back({i});
}
}
i++;
}
while(1){
if(st.empty())break;
auto top=st.back();
st.pop_back();
for(auto& x:top){
p_m[x].second=n;
p_m[x].first=st.empty()?-1:st.back().back();
}
}
for(int i=0;i<n;i++){
ret=max(ret,arr[i]*(p_m[i].second-p_m[i].first-1));
}
}
int largestRectangleArea(vector<int>& _heights) {
arr = _heights;
init(), solve();
return ret;
}
};全新版本
class Solution {
public:
vector<int> arr;
//下标-元素
int n;
//元素的个数
int ret;
//记录结果信息
using p = pair<int, int>;
vector<p> p_m;
//记录每一个元素左小于,右小于的信息
vector<int> st;
//vector模拟栈
void init() {
n = arr.size();
p_m.clear(), p_m.resize(n);
}
void solve() {
//首先维护每一个元素的左小于的信息
for (int i = 0; i < n; i++) {
while (1) {
//维护栈内单调性,严格的小到大
if (st.empty())
break;
if (arr[st.back()] < arr[i])
break;
st.pop_back();
//出栈,因为此时他们都不可能再作为某元素的左小于了.
}
//维护入栈元素的左小于信息
p_m[i].first = st.empty() ? -1 : st.back();
st.push_back(i);
//入栈
}
st.clear();
//栈清空
//维护所有元素的右小于信息
//此时必须是从后往前填写,因为对于j位置我需要找右小于,那么右边所有元素需要入栈并且栈保持单调
for (int i = n - 1; i >= 0; i--) {
while (1) {
if (st.empty())
break;
if (arr[st.back()] < arr[i])
break;
st.pop_back();
}
p_m[i].second = st.empty() ? n : st.back();
//维护右小于信息
st.push_back(i);
}
for (int i = 0; i < n; i++) {
ret = max(ret, arr[i] * (p_m[i].second - p_m[i].first - 1));
}
}
int largestRectangleArea(vector<int>& _heights) {
arr = _heights;
init(), solve();
return ret;
}
};85. 最大矩形
给定一个仅包含
0和1、大小为rows x cols的二维二进制矩阵，找出只包含1的最大矩形，并返回其面积。示例 1：
class Solution { public: vector<int> arr; //下标-元素 int n; //元素的个数 int ret; //记录结果信息 using p = pair<int, int>; vector<p> p_m; //记录每一个元素左小于,右小于的信息 vector<int> st; //vector模拟栈 void init() { n = arr.size(); p_m.clear(), p_m.resize(n); } void solve() { //首先维护每一个元素的左小于的信息 for (int i = 0; i < n; i++) { while (1) { //维护栈内单调性,严格的小到大 if (st.empty()) break; if (arr[st.back()] < arr[i]) break; st.pop_back(); //出栈,因为此时他们都不可能再作为某元素的左小于了. } //维护入栈元素的左小于信息 p_m[i].first = st.empty() ? -1 : st.back(); st.push_back(i); //入栈 } st.clear(); //栈清空 //维护所有元素的右小于信息 //此时必须是从后往前填写,因为对于j位置我需要找右小于,那么右边所有元素需要入栈并且栈保持单调 for (int i = n - 1; i >= 0; i--) { while (1) { if (st.empty()) break; if (arr[st.back()] < arr[i]) break; st.pop_back(); } p_m[i].second = st.empty() ? n : st.back(); //维护右小于信息 st.push_back(i); } for (int i = 0; i < n; i++) { ret = max(ret, arr[i] * (p_m[i].second - p_m[i].first - 1)); } } int largestRectangleArea(vector<int>& _heights) { arr = _heights; init(), solve(); return ret; } };输入：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'
1.
思路是每一行看作是柱状图的开始,那么题目完全转化为84. 柱状图中最大的矩形.
用dp记录每一个位置的柱状图高度.
每一行都计算一次,ret记录所有情况的最大值即可.
2.
入栈的时候维护信息.
一个循环维护左信息,一个循环维护右信息.
class Solution {
public:
vector<vector<char>> arr;
//arr表示矩形原始数据
int row, col;
//row和col表示矩形的行和列数
int ret;
//ret记录结果数据
vector<vector<int>> dp;
//dp记录所有位置的柱状图高度
vector<vector<int>> p_min;
//存储每一行的柱状图的左小于右小于信息
vector<int> st;
//模拟栈
void init() {
row = arr.size(), col = arr[0].size();
dp.clear(), dp.resize(row, vector<int>(col));
//计算dp值
for (int j = 0; j < col; j++) {
for (int i = 0; i < row; i++) {
if (arr[i][j] == '1')
dp[i][j] = 1 + (i - 1 >= 0 ? dp[i - 1][j] : 0);
else
dp[i][j] = 0;
}
}
p_min.clear(), p_min.resize(col, { 0, 0 });
//用{}大括号初始化vector,长度小的时候很方便
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}
//看一下dp值有没有计算计算错误
}
void solve() {
//正式开始解题
for (int i = 0; i < row; i++) {
//首先遍历每一行,表示每一个柱状图
p_min.clear(), p_min.resize(col, { 0, 0 });
st.clear();
//初始化左小于右小于信息
//初始化栈
for (int j = 0; j < col; j++) {
//先维护当前行的左小于信息
while (1) {
if (st.empty())break;
if (dp[i][j] > dp[i][st.back()])break;
st.pop_back();
}
p_min[j][0] = st.empty() ? -1 : st.back();
//维护当前j位置左小于信息
st.push_back(j);
//入栈
}
st.clear();
//栈清空
//维护右小于信息
for (int j = col - 1; j >= 0; j--) {
while (1) {
if (st.empty())break;
if (dp[i][j] > dp[i][st.back()])break;
st.pop_back();
}
p_min[j][1] = st.empty() ? col : st.back();
st.push_back(j);
}
//此时完成当前行的左小于右小于信息维护
//计算此时可能的矩形面积
for (int j = 0; j < col; j++) {
ret = max(ret, (p_min[j][1] - p_min[j][0] - 1) * dp[i][j]);
}
for (int j = 0; j < col; j++) {
cout << p_min[j][0] << " " << p_min[j][1] << " ";
}
cout << endl;
//打印看一下有没有问题
}
}
int maximalRectangle(vector<vector<char>>& _matrix) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
arr = _matrix;
init();
solve();
return ret;
}
};结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
