算法-最大矩形面积（解释思路）

有连续立柱，底边是1，高度不等2,1,5,6,2,3,4,6,6,2,1,2,3 求这些立柱中包含的最大矩形面积。如图所示，最大面积为12

最大矩形.png

• 暴力求解，每个立柱按照自己的高度左右延展至最大,时间复杂度O(n^2),空间复杂度O(1)
• 利用栈来求解。网上很多只说了算法的流程，而不讲解思路。各种算法多少有些差异，于是乎自己鲁了一个

package com.github.seahuang.algorithm;

import java.util.LinkedList;

public class Test {
    
    public static void main(String[] args){
        Integer[] pillars = new Integer[]{2,1,5,6,2,3,4,6,6,2,1,2,3};
        System.out.println(findMaxRectangleArea(pillars));
    }
    
    public static Integer findMaxRectangleArea(Integer[] pillars){
        if(pillars == null || pillars.length == 0){
            return null;
        }
        Integer maxRectangleArea = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        
        for(int i = 0; i < pillars.length; i++){//main loop
            //相等的情况，实际上是应该被跳过的（面积必然小于前面的下标），这里为了方便理解放一起
            if(stack.isEmpty() || pillars[i] >= pillars[stack.peek()]){
                //放入栈暂不处理。只要单调递增，矩形面积会不断增长
                stack.push(i);
                continue;
            }
            
            do{
                int shortest = stack.pop();
                int maxRectangleAreaCandidate =  (i - shortest) * pillars[shortest];
                maxRectangleArea = Math.max(maxRectangleArea, maxRectangleAreaCandidate);
            }while(!stack.isEmpty() && pillars[stack.peek()] > pillars[i]);//收割所有高于当前立柱的前驱
        }
        
        while(!stack.isEmpty()){//收割残余
            int shortest = stack.pop();
            int maxRectangleAreaCandidate = (pillars.length - shortest) * pillars[shortest];
            maxRectangleArea = Math.max(maxRectangleArea, maxRectangleAreaCandidate);
        }
        
        return maxRectangleArea;
    }
}

• 下面讲解下思路

• 随着下标从左到右，把这些个立柱看成会生长的矩形胚子-。-

• 整个程序主要有两个部分，“培养”和“收割”

• 单调递增部分即为“培养”，意味着随着下标右移，矩形可以持续变大。这时我们不忙着计算它的大小，而只是把它们(下标)押入栈中

  
  最大矩形-培养.png

• 单调递增后遇到的第一个下降的值，即开始“收割”。 收割谁？收割不再有成长可能性的立柱

  
  最大矩形-收割.png

• 如图中的3，4，6，6 被两边的2给挡住了。它们不再有机会增长出更大的内部矩形。所以可以收割。这里我们不断出栈，幷计算替换当前的最大矩形。直到栈内的立柱高度小于等于当前高度(最左边的2还可以继续增长)
• 虽然这个算法也是外层for循环套内层while循环。但是考虑到每个立柱只会进栈出栈一次。实际的时间是2n, 所以时间复杂度为O(n), 空间复杂度O(n)
• 为了简单期间，没有对单调递增期间相等的情况做特殊处理。实际上相等的立柱可以直接跳过，不压栈（左边的那个总是比右边的大）
• 另外我们循环过后要处理栈里剩余的值