四川网站建设免费咨询,网站要怎么运营,wordpress编写博客时如何写出代码,西安做行业平台网站的公司题目描述
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。
示例 1: 输入#xff1a;heights [2,1,5,6,2,3]
输出#xff1a;10
解释#xff1a;最…题目描述
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
示例 1: 输入heights [2,1,5,6,2,3]
输出10
解释最大的矩形为图中红色区域面积为 10示例 2 输入 heights [2,4]
输出 4提示
1 heights.length 1050 heights[i] 104
解答
class Solution {
public:int largestRectangleArea(vectorint heights) {
#if 0 // 双指针法vectorint minLeftIndex(heights.size());vectorint minRightIndex(heights.size());int size heights.size();// 记录每个柱子左边第一个小于该柱子的下标minLeftIndex[0] -1;for(int i 1; i size; i){int t i - 1;// 不断向左寻找while(t 0 heights[t] heights[i]) t minLeftIndex[t];minLeftIndex[i] t;}// 记录每个柱子右边第一个小于该柱子的下标minRightIndex[size - 1] size;for(int i size - 2; i 0; i--){int t i 1;// 不断向左寻找while(t size heights[t] heights[i]) t minRightIndex[t];minRightIndex[i] t;}int res 0;for(int i 0; i size; i){int sum heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);res max(sum, res);}return res;
#else // 单调栈栈顶到栈底要从大到小遇到比栈顶小的元素即计算可能结果// 栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求的最大面积的高度和宽度低高低int res 0;stackint st;// 数组头尾补上0heights.insert(heights.begin(), 0);heights.push_back(0);st.push(0);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()]){int mid st.top();st.pop();if(!st.empty()){int left st.top();int right i;int w right - left - 1;int h heights[mid];res max(res, w * h);}}}st.push(i);}return res;
#endif}
};
