leetcode84.柱状图中最大的矩形

题目链接

解法一：暴力求解

对于示例：[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).
执行结果如下：