LeetCode：柱状图中最大的矩形

文章收录于LeetCode专栏
LeetCode地址

柱状图中最大的矩形

题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例1

在这里插入图片描述

**输入：**heights = [2,1,5,6,2,3]
**输出：**10
**解释：**最大的矩形为图中红色区域，面积为 10

示例2

输入： heights = [2,4]
输出： 4

双指针暴力法

算法思路

算法题目是需要从给定的柱子中寻找两个柱子包裹形成面积最大矩形，即两个柱子间的间距为矩形的宽，两个柱子较短的一个的高为矩形的高。暴力法其实就是经过一次遍历，以每次得到的柱子的高度作为原点左右扩散，寻找第一个小于当前柱子高度的柱子作为边界。
为什么要寻找第一个小于当前柱子高度的柱子呐？因为只要有小于当前柱子高度的柱子，就说明不能再以当前遍历所得到的柱子的高度为矩形的高计算面积。
核心思想就是寻找第一个小于当前柱子高度的柱子作为边界。
在这里插入图片描述

编码

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length == 0){
            return 0;
        }
        int max = 0;
        for(int i=0; i<heights.length; i++){
            int height = heights[i];
            int leftWeight = 0;
            int rightWeight = 0;
            
            for(int j=i-1; j>=0; j--){
                // 向左寻找第一个小于height的柱子
                if(heights[j] < height){
                    break;
                }else{
                    leftWeight = leftWeight + 1;
                }
            }
            
            for(int k=i+1; k<heights.length; k++){
                // 向右寻找第一个小于height的柱子
                if(heights[k] < height){
                    break;
                }else{
                    rightWeight = rightWeight + 1;
                }
            }
            int temp = height * (leftWeight + rightWeight + 1);
            max = Math.max(temp, max);
        }
        return max;
    }
}

复杂度分析

因为整个算法没有使用额外的内存空间，所以空间复杂度为O(1)，时间复杂度为O( $N^2$ )。

栈辅助（单调栈）

算法思路

暴力法主要耗时在以某个柱子为高左右探测边界，那么有什么办法能避免左右探测边界的过程吗？
算法常用的套路就是用空间换时间，同样这里也可以使用一个栈来辅助完成最大面积的求解。之所以选择使用栈来做辅助空间，是因为可以在遍历柱子的过程中，使用栈先进后出的特性来构造一个单调递增的结构。
为什么要构造一个单调递增的结构呢？主要是因为只要后一个柱子的高度比前一个柱子高，则就可以将前一个柱子的高当做矩形的高。这样一来在遍历的过程中，只要后一个柱子比栈顶柱子（前一个柱子）的高度高，就入栈；如果后一个柱子比栈顶柱子矮，那么就需要将当前栈顶柱子出栈，并且以出栈柱子的高计算面积。
这里巧妙的利用单调递增的结构来避免了左右探测，之所以能这么做其核心思想还是寻找第一个小于以某个柱子为高计算面积的柱子作为边界。
特别注意，这里栈中存放的是柱子在数组中对应的位置，便于计算宽度。
在这里插入图片描述

编码

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length == 0){
            return 0;
        }
        
        int[] arrys = new int[heights.length + 2];
        for(int i=0; i<heights.length; i++){
            arrys[i+1] = heights[i];
        }
        
        int max = 0;
        
        // 定义栈用于构造单调递增结构
        Stack<Integer> stack = new Stack<>();
        // 放入arrys数组中第0位元素作为哨兵
        stack.push(0);
        for(int i=1; i<arrys.length; i++){
            while(arrys[i] < arrys[stack.peek()]){
                // 如果新入栈柱子的高度小于栈顶柱子的高度
                // 就将栈顶柱子出栈，并以此为高度计算面积
                int temp = arrys[stack.pop()] * (i - stack.peek() - 1);
                max = Math.max(max, temp);
            }
            // 新柱子入栈，保证栈内柱子单调递增
            stack.push(i);
        }    
        return max;
    }
}