柱状图中最大的矩形

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

1 2	输入: [2,1,5,6,2,3] 输出: 10

方法一：暴力法

矩形面积为宽乘高，我们可以固定其中一个，然后枚举另一个求出最大矩形面积。这里我们枚举高，使用一重循环枚举某一根柱子，将其固定为矩形的高度 h，随后我们以这根柱子为中心向左右两边扩散，当遇到高度比 h 小的柱子时停止，得到矩形的宽度 w，进而求出矩形面积 w*h。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len  = heights.length;
        if(len == 0){
            return 0;
        }
        int res = 0;
        //枚举每一根柱子
        for(int i = 0; i < len ; ++ i){
            int left = 0, right = 0;
			//寻找左边界
            for(left = i - 1 ; left >= 0 && heights[left] >= heights[i] ; --left);
            //寻找右边界
            for(right = i + 1 ; right < len && heights[right] >= heights[i] ; ++right);
			//计算结果
            res = Math.max(res, heights[i] * (right - left - 1));
        }
        return res;
    }
}

时间复杂度O(n^2) 空间复杂度 O(1)

方法二：单调栈

对于某一根柱子 i ，高度为 h = heights[i]。我们需要向两边扩展，找到左右两侧最近的高度小于 h 的柱子。先来看如何求一根柱子左侧且最近的小于其高度的柱子。

对于两根柱子，下标分别为 a 和 b，其中 a < b，且heights[a] >= heights[b]。在后面的柱子 i 向左照小于其高度的柱子时，由于柱子 a 的高度大于柱子 b 的高度，所以柱子 a 不可能成为柱子 i 左侧最近且小于其高度的柱子（应该是柱子 b），称为柱子 b 挡住了柱子 a。

这样一来，我们可以对数组从左到右进行遍历，同时维护一个可能作为答案的数据结构，其中按照从小到大存放柱子的下标值，并且它们的高度值也是单调递增的。如果有两个相邻的下标值不满足递增关系，则后者会挡住前者，前者不会作为答案。

我们在枚举到第 i 根柱子时，可以先将所有高度大于等于 heights[i] 的下标值全部移除，剩下的下标值中高度最高的即为答案。在这之后，我们将 i 放入数据结构中，开始接下来的枚举。

我们使用栈这一数据结构：

栈中存放了下标值 j。从栈底到栈顶，j 的值严格单调递增，同时对应的高度值也严格单调递增；
当我们枚举到第 i 根柱子时，我们从栈顶不断地移除 heights[j] >= heights[i] 的 j 值。在移除完毕后，栈顶的 j 值就一定满足 heights[j] < heights[i]。此时 j 就是 i 左侧最近的小于其高度的柱子；
再将 i 放入栈顶。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len  = heights.length;
        if(len == 0){
            return 0;
        }
        if(len == 1){
            return heights[0];
        }

        int area = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        //枚举每一根柱子
        for(int i = 0; i < len; i++){
            //栈顶的柱子 j 高度比当前柱子 i 的高度大，不满足递增关系。
            while(!stack.isEmpty() && heights[stack.peekLast()] > heights[i]){
                int height = heights[stack.removeLast()];
				//如果两个柱子高度相等不满足递增关系，出栈一个元素。
                while(!stack.isEmpty() && heights[stack.peekLast()] == height){
                    stack.removeLast();
                }
				
                int width;
                if(stack.isEmpty()){//栈为空，左侧的柱子都比柱子 i 高
                    width = i;
                }else{//栈非空，左侧最近比柱子 i 小的下标为栈顶元素的值
                    width = i - stack.peekLast() - 1;
                }
				//计算矩形面积
                area = Math.max(area, width * height);
            }
			//将柱子 i 添加到栈中
            stack.addLast(i);
        }
        	//考虑遍历完数组后栈中不为空的情况，例如高度数组为[1,2,3,4,5]。
            while(!stack.isEmpty()){
                int height = heights[stack.removeLast()];

                while(!stack.isEmpty() &&  heights[stack.peekLast()] == height){
                    stack.removeLast();
                }

                int width;
                if(stack.isEmpty()){
                    width = len;
                }else{
                    width = len - stack.peekLast() - 1;
                }

                area = Math.max(area, width * height);
            }
            return area;
    }
}

时间复杂度O(n) 空间复杂度 O(n)

我们还可以用哨兵来保持栈中不为空，这样少了很多判空处理。同时由于最后一个柱子高度为 0 可以清空栈，同时处理了高度数组为[1,2,3,4,5] 这种情况。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len  = heights.length;
        if(len == 0){
            return 0;
        }
        if(len == 1){
            return heights[0];
        }
        
        int area = 0;
        //高度数组首尾添加高度为 0 的两个柱子。
        int[] newHeights = new int[len + 2];
        for(int i = 0; i < len; i++){
            newHeights[i + 1] = heights[i];
        }
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>();
        //将高度为 0 的柱子下标加入栈中
        stack.addLast(0);
		// 从第一根高度不为 0 的柱子开始遍历。
        for(int i = 1; i < len; i++){
            //不可能有高度小于 0 的柱子，所以不需要判断栈是否为空
            while(heights[stack.peekLast()] > heights[i]){
                int height = heights[stack.removeLast()];
                //计算宽度
                int width = i - stack.peekLast() - 1;
                area = Math.max(area, width * height);
            }
            //将柱子 i 添加到栈中
            stack.addLast(i);
        }
            return area;
    }
}

时间复杂度，空间复杂度同上。