题意整理

  • 给定一个数组heights,长度为n,height[i]是在第i点的高度。
  • 每个height都表示一个直方图,宽度为1。求能组成的最大面积的矩形。

方法一(枚举)

1.解题思路

思路很简单,就是遍历每一个直方图,将其高度作为矩形的高度,然后分别向前、向后延申,得到可能的矩形的最大长度。计算每一个矩形的面积,取最大值即可。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        //总宽度
        int n=heights.length;
        int res=0;
        for(int i=0;i<n;i++){
            int start=-1;
            //从后往前找到第一个小于当前的高度,记为start
            for(int j=i-1;j>=0;j--){
                if(heights[j]<heights[i]){
                    start=j;
                    break;
                }
            }
            int end=n;
            //从前往后找到第一个小于当前的高度,记为end
            for(int j=i+1;j<n;j++){
                if(heights[j]<heights[i]){
                    end=j;
                    break;
                }
            }
            //根据start、end得到以当前高度为高的最大矩形面积,取所有可能的最大值
            res=Math.max(res,(end-start-1)*heights[i]);
        }        
        return res;
    }
}

3.复杂度分析

  • 时间复杂度:两层循环,最坏情况下所有元素相等,内层循环每次都要遍历n1n-1次,总共需要遍历n(n1)n*(n-1)次,所以时间复杂度是O(n2)O(n^2)
  • 空间复杂度:需要额外常数级别的空间,所以空间复杂度为O(1)O(1)

方法二(单调栈)

1.解题思路

  • 新建单调栈,通过单调栈维护一个单调不递减的序列的下标。
  • 只要栈顶元素比当前大,则可以统计以栈顶元素为高的最大面积。由于单调栈内元素是单调不递减的,可以确定矩形右边界为当前元素前一位,而左边界为弹栈后栈顶元素后一位。如果栈中元素为空,说明0为左边界,因为单调不递减,后面的肯定比它大,前面的比他小,而为空,说明已经没有比它小的了,之前弹出的元素也一定比它大,所以左边界要从0开始。
  • 如果遍历完之后,单调栈还不为空,则以同样的方式继续统计可能的最大面积。

图解展示: alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        //总宽度
        int n=heights.length;
        //新建单调栈
        ArrayDeque<Integer> stack=new ArrayDeque<>();
        
        int res=0;
        for(int i=0;i<n;i++){
            //只要栈顶元素比当前大,则可以统计以栈顶元素为高的最大面积
            while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
                //由于单调栈内元素是单调不递减的,L到i-1之间的高度一定大于等于curHeight
                int curHeight=heights[stack.pop()];
                //如果栈中元素为空,说明0到i-1之间的高度均大于等于curHeight
                int L=stack.isEmpty()?0:stack.peek()+1;
                res=Math.max(res,(i-L)*curHeight);
            }
            stack.push(i);
        }
        
        //如果遍历完之后,单调栈还不为空,则继续统计可能的最大面积
        while(!stack.isEmpty()){
            int curHeight=heights[stack.pop()];
            int L=stack.isEmpty()?0:stack.peek()+1;
            res=Math.max(res,(n-L)*curHeight);
        }
        
        return res;
    }
}

3.复杂度分析

  • 时间复杂度:每个元素最多进栈和出栈一次,所以时间复杂度是O(n)O(n)
  • 空间复杂度:需要额外大小为n的栈,所以空间复杂度为O(n)O(n)