package com.LC;

//import java.util.ArrayDeque;
//import java.util.Deque;
//
//public class Solution {
//    public int largestRectangleArea(int[] heights) {
//        int len = heights.length;
//        if (len == 0) {
//            return 0;
//        }
//
//        if (len == 1) {
//            return heights[0];
//        }
/////////////////////////////////////////
//        int res = 0;
/////////////扩充数组长度////////////////////////
//        int[] newHeights = new int[len + 2];//增加了两个长度
//        newHeights[0] = 0;// 新数组的第一位是0
//        System.arraycopy(heights, 0, newHeights, 1, len);
//        newHeights[len + 1] = 0;// 新数组的最后一位是0
//        len += 2;
//        heights = newHeights;
///////////////////////////////////////////////////
//// Java集合提供了接口Deque来实现一个双端队列，它的功能是：
//// 既可以添加到队尾，也可以添加到队首；
//// 既可以从队首获取，又可以从队尾获取。
//        Deque<Integer> stack = new ArrayDeque<>(len);//长度为len
//        // 先放入哨兵，在循环里就不用做非空判断
//        stack.addLast(0); //
//
//        for (int i = 1; i < len; i++) {
//            while (heights[i] < heights[stack.peekLast()]) { //右边严格小于 获取队尾元素但不删除
//                int curHeight = heights[stack.pollLast()]; //(记录当前柱状体的高度,同时,柱状体边长向左拓展)
//                int curWidth = i - stack.peekLast() - 1; //(边长向左拓展的时候stack.peekLast() 值减少 curwidth的值在增加)取队尾元素但不删除 队尾先进后厨
//                res = Math.max(res, curHeight * curWidth);
//            }
//            stack.addLast(i); //将数组下标添加到队尾
//        }
//        return res;
//    }
//
//    public static void main(String[] args) {
//         int[] heights = {2, 1, 5, 6, 2, 3};
////        int[] heights = {1, 1};
//        Solution solution = new Solution();
//        int res = solution.largestRectangleArea(heights);
//        System.out.println(res);
//    }
//}

// @lc code=start

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }

        if (len == 1) {
            return heights[0];
        }
///////////////////////////////////////
        int res = 0;
///////////扩充数组长度////////////////////////
        int[] newHeights = new int[len + 2];//增加了两个长度
        newHeights[0] = 0;// 新数组的第一位是0
        System.arraycopy(heights, 0, newHeights, 1, len);
        newHeights[len + 1] = 0;// 新数组的最后一位是0
        len += 2;
        heights = newHeights;
/////////////////////////////////////////////////
// Java集合提供了接口Deque来实现一个双端队列，它的功能是：
// 既可以添加到队尾，也可以添加到队首；
// 既可以从队首获取，又可以从队尾获取。
        Deque<Integer> stack = new ArrayDeque<>(len);//长度为len
        // 先放入哨兵，在循环里就不用做非空判断
        stack.addLast(0); //
        for (int i = 1; i < len; i++) {
            while (heights[i] < heights[stack.peekLast()]) {
//          while (heights[i] < heights[i + 1]) {
                int curHeight = heights[stack.pollLast()]; //记录栈顶并出站
                int curWidth = (i - stack.peekLast()-1); //计算width后并将指针向左移两位
                res = Math.max(res ,curHeight * curWidth);
            }
            stack.addLast(i);//计算width
        }
        return res;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
//        int[] heights = {1, 1};
        Solution solution = new Solution();
        int res = solution.largestRectangleArea(heights);
        try (Scanner scanner = new Scanner(System.in)) {
          String content = scanner.nextLine();

        }
        System.out.println(res);
//        System.out.println("You enter"+x);

    }
}