leetcode之每日一题

leetcode 84

柱状图中最大的矩形

Posted by Static on May 30, 2020

题目链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

题目描述

分析

1. 暴力

时间负责度:O(n^2)

从左侧遍历，获取最小的高度，宽度即使数组的下标，则最大面积=高度*宽度

代码实现

public enum Q84 {
    instance;

    // 暴力
    public int largestRectangleArea(int[] heights) {
        if(heights.length==0)return 0;
        if(heights.length==1)return heights[0];

        int size=heights.length;
        int maxArea=0;

        for(int i=0;i<size;i++){
            int height=Integer.MAX_VALUE;
            for(int j=i;j<size;j++){
                height=height>heights[j]?heights[j]:height;
                int area=height*(j-i+1);
                maxArea=area>maxArea?area:maxArea;
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        // assert 10
        SystemUtil.print(Q84.instance.largestRectangleArea(new int[]{2,1,5,6,2,3}));
        // assert 15
        SystemUtil.print(Q84.instance.largestRectangleArea(new int[]{2,1,6,6,2,5,5,5,3}));
    }
}