189 8069 5689
给定 n n n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的大面积。
示例1：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：大的矩形为图中红色区域，面积为 10示例2：
输入： heights = [2,4]
输出： 4class Solution {public:
int largestRectangleArea(vector& heights) {}
}; 84. 柱状图中大的矩形
二、解题报告 1、思路分析例子：
那么大的长方形面积是如下图中的红色区域：
整体思路就是 必须以每个位置的直方图作为高的长方形能扩多远，遇到相同的高度时进行错化处理，最终是能计算正确的。
如何找到以每个位置的直方图作为高的长方形能扩充的范围呢？
找到每个位置左右最近的比它矮的直方图，除了这两个位置不能到达，其他位置就是它所能扩充的范围。
2、时间复杂度O ( n ) O(n) O(n)
3、代码详解//不使用系统stack的解法
class Solution {public:
int largestRectangleArea(vector& heights) {if (heights.size() == 0) return 0;
int n = heights.size();
int _stack[n]; //准备一个栈，此处使用数组替代系统栈
memset(_stack, 0, sizeof(_stack));
int si = -1;
int ans = 0;
for (int i = 0; i< n; i++) {while (si != -1 && heights[_stack[si]] >= heights[i]) {//栈不为空 且 栈顶元素对应的值>=当前元素位置对应的值
int cur = heights[_stack[si--]]; //获取栈顶位置的直方图高度
int left = si == -1 ? -1 : _stack[si]; //找到左边最近的比栈顶位置直方图低的位置
ans = max(ans, (i - left - 1) * cur); //右边最近的比栈顶位置直方图低的是i位置
//所以以cur为高度的长方形能扩充的范围就是[left + 1, i - 1],宽度为(i - left - 1)
}
_stack[++si] = i;
}
while (si != -1) {//遍历完数组后，栈中还有数据，则单独结算
int cur = heights[_stack[si--]];
int left = si == -1 ? -1 : _stack[si];
ans = max(ans, (n - left - 1) * cur);
}
return ans;
}
}; //使用系统stack的解法
class Solution {public:
int largestRectangleArea(vector& heights) {if (heights.size() == 0) return 0;
stacksta;
int area = 0;
for (int i = 0; i< heights.size(); i++) {while (!sta.empty() && heights[sta.top()] >= heights[i]) {int j = sta.top();
sta.pop();
int k = sta.empty() ? -1 : sta.top();
area = max(area, (i - k - 1) * heights[j]);
}
sta.push(i);
}
while (!sta.empty()) {int j = sta.top();
sta.pop();
int k = sta.empty() ? -1 : sta.top();
int curArea = (heights.size() - k - 1) * heights[j];
area = max(area, curArea);
}
return area;
}
}; public class LargestRectangleInHistogram {//使用系统栈
public static int largestRectangleArea1(int[] height) {if (height == null || height.length == 0) { return 0;
}
int maxArea = 0;
Stackstack = new Stack();
for (int i = 0; i< height.length; i++) { while (!stack.isEmpty() && height[i]<= height[stack.peek()]) { int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack.push(i);
}
while (!stack.isEmpty()) { int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
//使用数组替代系统栈
public static int largestRectangleArea2(int[] height) {if (height == null || height.length == 0) { return 0;
}
int N = height.length;
int[] stack = new int[N];
int si = -1;
int maxArea = 0;
for (int i = 0; i< height.length; i++) { while (si != -1 && height[i]<= height[stack[si]]) { int j = stack[si--];
int k = si == -1 ? -1 : stack[si];
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack[++si] = i;
}
while (si != -1) { int j = stack[si--];
int k = si == -1 ? -1 : stack[si];
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧