直方图内最大矩形

题目描述

给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少?

1.每个直方图宽度都为1

2.直方图都是相邻的

3.如果不能形成矩形，返回0即可

4.保证返回的结果不会超过2^31-1

方法一：暴力解法

解题思路

对于本题目的求解，直接遍历每一个直方图，将其高度作为矩形的高度，然后分别向前、向后延申，得到可能的矩形的最大长度，然后计算每个矩形的面积，最后取最大值即可。

alt

解题代码

import java.util.*;

public class Solution {
    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;//返回结果
    }
}

复杂度分析

时间复杂度：两层循环，因此时间复杂度为O(N2)O(N^2)。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为O(1)O(1)。

方法二：栈思想

解题思路

对于本题目的求解，可以使用单调栈，只要栈顶元素比当前大，则可以统计以栈顶元素为高的最大面积。由于单调栈内元素是不减的，可以确定矩形右边界为当前元素前一位，而左边界为pop操作以后栈顶元素的后一位。如果栈中元素为空，说明0为左边界，因为单调不递减，后面的肯定比它大，前面的比它小，若为空，则说明左边界为0。如果遍历完之后，单调栈还不为空，则以同样的方式继续统计面积值，最后返回最大值即可。

alt

解题代码

import java.util.*;

public class Solution {
    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; // 返回面积最大值
    }
}

复杂度分析

时间复杂度：一层循环，因此时间复杂度为O(N)O(N)。

空间复杂度：使用大小为N的栈，因此空间复杂度为O(N)O(N)。