package com.stack;

import java.util.Stack;
/**
 * 给定一个非负数组arr,代表直方图
 * 返回直方图的最大长方形面积
 * 测试链接:https://leetcode.com/problems/largest-rectangle-in-histogram
 * */
public class LargestRectangleInHistogram {

 public static int largestRectangleArea1(int[] height){
 if (height == null || height.length == 0){
 return 0;
 }
 int N = height.length;
 int maxArea = 0;
 int curArea = 0;
 Stack<Integer> stack = new Stack<>();
 for (int i = 0; i < N; i++) {
 while (!stack.isEmpty() && height[i] <= height[stack.peek()]){
 int j = stack.pop();
 int leftLessIndex = (stack.isEmpty() ? -1:stack.peek());
 curArea = (i - leftLessIndex -1) * height[j];
 maxArea = Math.max(maxArea,curArea);
 }
 stack.push(i);
 }
 /**
 * 设i=n时,如果while表达式中的判断值为true,则会一直执行上面的while循环,而不会执行下面的stack.push(i);
 * 上面的while循环,会计算arr[(i-1)...(i-1)]、arr[(i-2)...(i-1)]、arr[(i-3)...(i-1)]直到arr[0...(i-1)],
 * 计算出面积并逐个比较大小
 * 经过上面的while循环后,已经计算出arr[0...(i-1)]范围上的最大面积
 * */
 while (!stack.isEmpty()){
 int j = stack.pop();
 int leftLess = (stack.isEmpty() ? -1 : stack.peek());
 curArea = (N - leftLess - 1) * height[j];
 maxArea = Math.max(maxArea,curArea);
 }
 return maxArea;
 }

 public static int largestRectangleArea2(int[] height){
 if (height == null || height.length == 0){
 return 0;
 }
 int N = height.length;
 int maxArea = 0;
 int curArea = 0;
 int si = -1;
 int[] stack = new int[N];
 for (int i = 0; i < N; i++) {
 while (si != -1 && height[i] <= height[stack[si]]){
 int j = height[si--];
 int leftLessIndex = (si == -1 ? -1: stack[si]);
 curArea = (i - leftLessIndex -1) * height[j];
 maxArea = Math.max(maxArea,curArea);
 }
 stack[++si] = i;
 }
 /**
 * 设i=n时,如果while表达式中的判断值为true,则会一直执行上面的while循环,而不会执行下面的stack.push(i);
 * 上面的while循环,会计算arr[(i-1)...(i-1)]、arr[(i-2)...(i-1)]、arr[(i-3)...(i-1)]直到arr[0...(i-1)],
 * 计算出面积并逐个比较大小
 * 经过上面的while循环后,已经计算出arr[0...(i-1)]范围上的最大面积
 * */
 while (si != -1){
 int j = stack[si--];
 int leftLess = (si == -1 ? -1 : stack[si]);
 curArea = (N - leftLess - 1) * height[j];
 maxArea = Math.max(maxArea,curArea);
 }
 return maxArea;
 }
}