Leetcode 84. 柱状图中最大的矩形（困难）

题意： 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路： 我们对于每个柱子都构造一个专属于他的最大矩形 我们从左往右观察，对于当前柱子能与他右边各柱子构成的最大矩形是什么情况呢？是找到他右边第一个比他矮的柱子的左侧，这样专属于当前柱子的最大矩形的面积是长度*当前柱子的高度。 那么这个问题就转化为 找到数组中 对于每个元素 其右侧第一个比他小的元素的下标-1 这是单调栈的入门题目 剩下的不再赘述。

public int largestRectangleArea(int[] heights) {
          
   
        Stack<Integer> stack=new Stack<>();
        int n=heights.length;
        int r[]=new int[n];
        for(int i=0;i<n;i++){
          
   
            if(stack.isEmpty()||heights[stack.peek()]<=heights[i]){
          
   
                stack.add(i);
            }else{
          
   
                while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
          
   
                    int temp=stack.pop();
                    r[temp]=i-1-temp;
                }
                stack.add(i);
            }
        }
        while(!stack.isEmpty()){
          
   
            int temp=stack.pop();
            r[temp]=n-temp-1;
        }
        int l[]=new int[n];
        for(int i=n-1;i>=0;i--){
          
   
            if(stack.isEmpty()||heights[stack.peek()]<=heights[i]){
          
   
                stack.add(i);
            }else{
          
   
                while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
          
   
                    int temp=stack.pop();
                    l[temp]=temp-i-1;
                }
                stack.add(i);
            }
        }
        while(!stack.isEmpty()){
          
   
            int temp=stack.pop();
            l[temp]=temp;
        }
        int ans=0;
        for(int i=0;i<n;i++){
          
   
            ans=Math.max(ans,(l[i]+r[i]+1)*heights[i]);
        }
        return ans;
    }

时间复杂度 O(N) 空间复杂度 O(N)