84. 柱状图中最大的矩形

package stack.code84;
import java.util.Stack;
public class Solution {
    public int largestRectangleArea(int[] heights) {
        //用作返回的答案
        int res = 0;
        //用来存储满足单调性的矩形的栈
        Stack<Rect> stack = new Stack<>();
        //在数组后面增加一个0，是代码整洁，最后可以清空栈
        heights = arrPushBack(heights,0);
        //遍历数组，也就是便利矩形网格
        for(int height : heights){
            //记录累加宽度
            int leijiaWidth = 0;
            //如果栈不为空且
            //栈顶矩形的高度，大于当前高度了。说明单调性被破坏了。则需要进行如下操作
            while (!stack.isEmpty() && stack.peek().heigh >= height){
                leijiaWidth = stack.peek().width + leijiaWidth;
                res = Math.max(res,stack.peek().heigh * leijiaWidth);
                stack.pop();
            }
            stack.push(new Rect(leijiaWidth + 1,height));
        }
        return res;
    }
    public int[] arrPushBack(int[] arr,int value){
        int[] newArr = new int[arr.length + 1];
        for(int i = 0 ; i < arr.length;i++){
            newArr[i] = arr[i];
        }
        newArr[arr.length] = value;
        return newArr;
    }
    /**
     * 定义一个矩形对象，有宽和高两个属性
     */
     class Rect{
        int width;
        int heigh;
        public Rect(int width, int heigh) {
            this.width = width;
            this.heigh = heigh;
        }
    }
}