leetcode:84. 柱状图中最大的矩形

快来打我* 2023-06-25 04:38 3阅读 0赞

## 题目: ##

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 \[2,1,5,6,2,3\]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

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

## 分析: ##

这题有点东西,有三种思路,大概看一下  
思路1:自然产生的思路,循环之后以每一个为左边计算可获得的最大面积,O(n2)  
思路2:分治,看到别人的思路后也能做出来  
思路3:单调栈  
其实对于数组中每一个节点来说,计算最大面积就是向两边找第一个比自己小的数的坐标,遍历数组,维护一个栈  
如果当前值大于等于栈顶值就push进去,否则说明对于栈顶来说,当前就是右边第一个小于他的数,而左边第一个小于他的数就是栈里前一个坐标,所以把栈顶pop出来,用高度\*当前坐标-pop后栈顶坐标的面积,更新计算面积,为了防止有的值找不到左右小于他的数,在数组左右加两个0

## 代码: ##

思路1:

class Solution {
        public int largestRectangleArea(int[] heights) {
            int l = heights.length;
            if (l == 0) {
                return 0;
            }
            if (l == 1) {
                return heights[0];
            }
            int max = heights[0];
            //i代表矩形左边
            for (int i = 0; i < l; i++) {
                int minHeight = heights[i];
                //j代表矩形右边
                for (int j = i; j < l; j++) {
                    minHeight = Math.min(minHeight, heights[j]);
                    max = Math.max((j - i + 1) * minHeight, max);
                }
            }
            return max;
        }
    }

思路2:

public int largestRectangleArea(int[] heights) {
            return largestRectangleArea(heights, 0, heights.length - 1);
        }
    
        private int largestRectangleArea(int[] heights, int start, int end) {
            if (start < 0 || end > heights.length - 1 || end < start) {
                return 0;
            }
            if (start == end) {
                return heights[start];
            }
            int minHeightIndex = start;
            for (int i = start; i <= end; i++) {
                if (heights[i] < heights[minHeightIndex]) {
                    minHeightIndex = i;
                }
            }
            return Math.max((end - start + 1) * heights[minHeightIndex], Math.max(largestRectangleArea(heights, start, minHeightIndex - 1), largestRectangleArea(heights, minHeightIndex + 1, end)));
        }

思路3:

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

## 效率: ##

## 总结: ##