网站开发网上悼念,大气企业网站模板,福州企业名录,网络营销课程免费一、84.柱状图中最大的矩形
力扣题目链接
42接雨水 是找每个柱子左右两边第一个大于该柱子高度的柱子#xff0c;而本题是找每个柱子左右两边第一个小于该柱子的柱子。
本题是要找每个柱子左右两边第一个小于该柱子的柱子#xff0c;所以从栈头#xff08;元素从栈头弹出…一、84.柱状图中最大的矩形
力扣题目链接
42接雨水 是找每个柱子左右两边第一个大于该柱子高度的柱子而本题是找每个柱子左右两边第一个小于该柱子的柱子。
本题是要找每个柱子左右两边第一个小于该柱子的柱子所以从栈头元素从栈头弹出到栈底的顺序应该是从大到小的顺序
主要就是分析清楚如下三种情况
情况一当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况情况二当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况情况三当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
// 版本一
class Solution {
public:int largestRectangleArea(vectorint heights) {int result 0;stackint st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈从下标1开始for (int i 1; i heights.size(); i) {if (heights[i] heights[st.top()]) { // 情况一st.push(i);} else if (heights[i] heights[st.top()]) { // 情况二st.pop(); // 这个可以加可以不加效果一样思路不同st.push(i);} else { // 情况三while (!st.empty() heights[i] heights[st.top()]) { // 注意是whileint mid st.top();st.pop();if (!st.empty()) {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;}
};
