【每日一题-leetcode】84.柱状图中最大的矩形

84.柱状图中最大的矩形

84. 柱状图中最大的矩形

难度困难509收藏分享切换为英文关注反馈

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

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

示例:

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

1.暴力破解

思路

两层遍历确定每一层最大的面积，第三层循环确定每次最底的高， j-i+1 长 * 高 求出每次的面积

time:O(n^3)

space:O(1)

 public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        for(int i=0;i<heights.length;i++){ //多少轮
            for(int j=i;j<heights.length;j++){ //多少次
                int minHeigh = Integer.MAX_VALUE;
                for(int k=i;k<=j;k++)//每一次中最小值
                    minHeigh = Math.min(minHeigh,heights[k]);

                maxArea = Math.max(maxArea,minHeigh*(j-i+1));//每一次计算出最大值
            }
        }
        return maxArea;
    }

2.优化暴力

思路：每次利用之前的最低高

time:O(n^2)

space:O(1)

public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        for(int i=0;i<heights.length;i++){ //多少轮
            int minHeigh = Integer.MAX_VALUE;
            for(int j=i;j<heights.length;j++){ //多少次
                minHeigh = Math.min(minHeigh,heights[j]);
                maxArea = Math.max(maxArea,minHeigh*(j-i+1));//每一次计算出最大值
            }
        }
        return maxArea;
    }

3.栈

time:O(n)

space:O(n)

   public int largestRectangleArea(int[] heights) {
            Stack < Integer > stack = new Stack < > ();
            stack.push(-1);
            int maxarea = 0;
            for (int i = 0; i < heights.length; ++i) {
                while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                    maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
                stack.push(i);
            }
            while (stack.peek() != -1)
                maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
            return maxarea;
        }