|
LeetCode 84. 柱状图中最大的矩形 | C语言版
LeetCode 84. 柱状图中最大的矩形题目描述解题思路思路一：使用栈代码实现运行结果参考文章：[https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html#%E5%8D%95%E8%B0%83%E6%A0%88](https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html#%E5%8D%95%E8%B0%83%E6%A0%88)
思路二：减少遍历节点数代码实现运行结果参考文章：[]()
LeetCode 84. 柱状图中最大的矩形
题目描述
题目地址：84. 柱状图中最大的矩形 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
解题思路
思路一：使用栈
代码实现
class Solution {
public:
int largestRectangleArea(vector& heights) {
//42. 接雨水和 739. 每日温度 是找每个柱子左右两边第一个大于该柱子高度的柱子，单调栈从栈头到栈底的顺序是从小到大；而本题是找每个柱子左右两边第一个小于该柱子的柱子，单调栈从栈头到栈底的顺序是从大到小
//什么是单调栈？单调栈就是保持栈内元素有序
//单调栈使用情景？通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了
//柱状图中的最大矩形：栈头元素就是中间的柱子，栈头第二个元素就是左边的小柱子（比中间柱子小得柱子），而添加的元素就是右边的小柱子。栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
//单调栈
stack st;
//数组头部加入元素0
heights.insert(heights.begin(),0);
//数组尾部加入元素0
heights.push_back(0);
st.push(0);
int result=0;
//第一个元素已经入栈，从下标1开始
for(int i=1;i
st.push(i);
}
//如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
else if(heights[i]==heights[st.top()]){
st.pop();
st.push(i);
}
//如果当前遍历的元素（柱子）高度小于栈顶元素的高度，此时以最小柱子为标准，算柱状图中的最大矩形
else{
while(!st.empty() && heights[i]
int left=st.top();
int right=i;
int w=right-left-1;
int h=heights[mid];
result=max(result,w*h);
}
}
st.push(i);
}
}
return result;
}
};
运行结果
参考文章：https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html#%E5%8D%95%E8%B0%83%E6%A0%88
思路二：减少遍历节点数
代码实现
在这里插入代码片
运行结果
参考文章：
|