力扣刷题记录 -- JAVA---137--84. 柱状图中最大的矩形

一、题目

二、代码

class Solution 
{
    //类比贪心   局部最优到全局最优
    //左边第一个小于的下标   右边第一个小于的下标   
    public int largestRectangleArea(int[] heights) 
    {
         int i;
         int length = heights.length;
         int[] left_low = new int [length];
         int[] right_high = new int [length];
         int max_size = 0;

         left_low[0] = -1;
         right_high[length-1] = length;

         for(i=1;i<length;i++)
         {
             int t = i-1;
             while(t>=0&&heights[t]>=heights[i]) t = left_low[t];
             left_low[i] = t;
            //  System.out.println(" 左侧  ");
            //  System.out.println("  i  "+i+"  t "+t);
         }

         for(i=length-2;i>=0;i--)
         {
             int t = i+1;
             while(t<=length-1&&heights[t]>=heights[i]) t = right_high[t];
             right_high[i] = t;
         }

         for(i=0;i<length;i++)
         {

            int temp = heights[i]*(right_high[i] - left_low[i]-1);
            // System.out.println("   i   " + i);

            // System.out.println("   right_high[i]   " + right_high[i]);
            // System.out.println("    left_low[i]   " +  left_low[i]);

            // System.out.println("   temp   " + temp);
            max_size = Math.max(temp,max_size);
         }

         return max_size;

    }
}

三、运行结果