力扣hot100 84题柱状图中最大的矩形 打卡_力扣84题

84. 柱状图中最大的矩形

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

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

解题思路：我们可以遍历数组中的每一个元素，将该元素作为矩形的高，则矩形的长则是两边元素首先小于该元素的位置之间的长度。

我们可以直接用暴力的办法，对于每个元素都用循环的方式来找它最左边首先小于它的元素以及最右边首先小于他的元素，但是O(n2)的时间复杂度肯定会超时。

方式一：暴力，但是我提交的时候发现只有两组测试用例过不了，分别是8035和8783，他们数组长度太长了，并且数组每个元素都是他们自己本身，所以时间复杂度直接拉满，但是我们可以当狗也是能过滴，但是并没有什么卵用，看截图：

 方式二：单调栈

今天学习了单调栈的用法，根据暴力的思想，其实我们的任务就变成了如何在On的时间复杂度内找到每一个元素两边第一个比他小的元素，我们可以使用单调栈的方法来解决。代码和提交截图如下：

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

总结：单调栈的使用有一个瑕疵，虽然不影响最后的结果，因为我们这种写法在压栈的时候没有考虑相等的因素，虽然能过，但是心里还是不怎么舒服。