解法一：暴力求解
对于示例：[2,1,5,6,2,3]
首先遍历一遍柱子，遍历到的柱子作为“左边界”，从左边界开始向右扩展，通过左右边界范围内的最低高度来计算出最大的矩形面积。具体的思路其实比较简单，见代码即可：
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
for(int i = 0;i < heights.length;i++){
int minHeight = Integer.MAX_VALUE;
for(int j = i;j < heights.length;j++){
minHeight = Math.min(minHeight,heights[j]);
maxArea = Math.max(maxArea,minHeight * (j - i + 1));
}
}
return maxArea;
}
}
该算法的时间复杂度为O(n^2),额外空间复杂度为O(1)
执行结果如下：
解法二：Stack
本思路中，使用了栈这种数据结构，对于示例：[2,1,5,6,2,3]的图解如下：
首先将2 push到栈中
接着遍历到1这个元素上，因为
1 < 2，所以将栈元素pop至小于等于1的位置，本示例相当于把2出栈。并计算出此时最大的面积为 2，接着我们不断遍历到第二个递增栈
因为
2 < stack.peek() 所以第二个递增栈为图示的部分，我们发现了2 < 6所以将6这个元素pop出栈，此时记录的面积为 6 * 1 = 6。此时栈顶的元素为5依然大于2，所以还需要继续将5这个元素pop出栈，此时的最大面积就为：
5 * 2 = 10了，直至1 < 2, 停止出栈，继续向栈中push剩余的元素，此时栈内的元素情况为：
遍历一遍所有的柱子，栈不为空，我们需要对剩余的柱子求出构成的最大面积，首先pop出3，当前记录的面积为3，pop出2，当前记录的面积为
2 * 4 = 8,对于栈中最后剩余的元素1来说，当前记录的面积为1 * 6 = 6。所以最后结论可以得出最大的面积为10。代码如下：
class Solution {
public int largestRectangleArea(int[] heights) {
if(heights == null || heights.length == 0){
return 0;
}
if(heights.length == 1){
return heights[0];
}
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
stack.push(-1);
for(int i = 0;i < heights.length;i++){
while(stack.peek() != -1 && heights[i] <= heights[stack.peek()]){
maxArea = Math.max(maxArea,heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
while(stack.peek() != -1){
maxArea = Math.max(maxArea,heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return maxArea;
}
}
为什么代码中，需要向stack中先push一个-1？因为我们需要在遍历一遍数组时包括在stack不为空的情况时，考虑到所有最大面积的情况，试想这样一个示例：[2,1,2]
对于这样一个示例来说，最大面积为3。遍历一遍数组后，我们得到最大面积为2而不是3。而遍历后，stack不为空，stack中的元素为1和2，我们需要计算出stack剩余元素所能构成的最大面积，对于元素1来说，最大面积为：1 * 3 = 3；所以如果设置了一个栈底元素-1，我们就可以使用这样的方法去计算：heights[stack.pop()] * (heights.length - stack.peek() - 1));，还请仔细体会。
该算法的时间复杂度为O(n),因为使用了栈这种数据结构，所以额外空间复杂度为O(n).
执行结果如下：
网友评论