题目: 给定n个非负整数,用来表示柱状图中各个柱子的高度;每个柱子彼此相邻,且宽度为1;求在该柱状图中,能够勾勒出来的矩形的最大面积;
              __    
           __|__|  
          |__|__|
          |__|__|   __
     __   |__|__|__|__|  
    |__|__|__|__|__|__|
    |__|__|__|__|__|__|
    输入: [2,1,5,6,2,3]
    输出: 10
1.枚举"宽":
    [1]思路: 使用两重循环枚举矩形的左右边界获取到任意边界组合的最大面积
        (1)外层循环的循环变量为左边界,内层循环的循环变量为右边界;
        (2)在左右边界内获取最小高度作为矩形的高,并以此来计算面积;
    [2]实现:
        class Solution {
            public int largestRectangleArea(int[] heights) {
                // 数组长度
                int n = heights.length;
                // 定义最大面积变量
                int maxArea = 0;
                // 循环左边界
                for (int left = 0; left < n; left++) {
                    // 定义最低高度变量
                    int minHeight = Integer.MAX_VALUE;
                    // 循环右边界
                    for (int right = left; right < n; right++) {
                        // 获取对应边界范围内的最低高度
                        minHeight = Math.min(minHeight,heights[right]);
                        // 计算最大面积
                        maxArea = Math.max(maxArea,(right-left+1)*minHeight);
                    }
                }
                return maxArea;
            }
        }
    [3]复杂度分析:
        (1)时间复杂度: O(n^2)
        (2)空间复杂度: O(n^2)
2.枚举"高":
    [1]思路: 
        (1)遍历数组中的高,并在遍历到的高的两侧延伸到不低于当前高的最远位置;
        (2)求出该范围的最大矩形面积: 当前高*(右边界-左边界+1)
    [2]实现: 
        class Solution {
            public int largestRectangleArea(int[] heights) {
                // 数组长度
                int n = heights.length;
                // 定义最大面积变量
                int maxArea = 0;
                for (int i = 0; i < n; i++) {
                    // 枚举高(当前遍历到的高)
                    int hetght = heights[i];
                    int left = i, right = i;
                    // 确定左右边界
                    while (left - 1 >= 0 && heights[left - 1] >= hetght) {
                        left--;
                    }
                    while (right + 1 < n && heights[right + 1] >= hetght) {
                        right++;
                    }
                    // 计算面积
                    maxArea = Math.max(maxArea, hetght * (right - left + 1));
                }
                return maxArea;
            }
        }
    [3]复杂度分析:
        (1)时间复杂度: O(n^2)
        (2)空间复杂度: O(1)
3.枚举"高"+单调栈:
    [1]思路: 在枚举"高"中,每个下标的元素都会纳入到边界内多次,通过单调栈保证一次遍历中每个下标只入栈和出栈一次
        (1)使用两个数组分别用来保存遍历到的元素对应的左边界左侧元素的下标和右边界右侧元素的下标
        (2)使用单调栈的判断处理逻辑来确定左边界左侧元素的下标和右边界右侧元素的下标并保存到数组
        (3)根据两个数组中的边界情况计算最大面积
    [2]实现:
        (1)版本1:
            class Solution {
                public int largestRectangleArea(int[] heights) {
                    // 数组长度
                    int n = heights.length;
                    int[] left = new int[n];
                    int[] right = new int[n];
                    // 定义一个双端队列对象作为"栈"
                    Deque<Integer> stack = new ArrayDeque<>();
                    // 从左到右遍历数组,每次保留栈顶元素(数组下标)
                    for (int i = 0; i < n; i++) {
                        // 判断当前遍历到的元素与栈顶的下标对应的元素进行比较大小
                        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                            stack.pop();
                        }
                        // 如果栈中为空,则返回-1,否则返回栈顶元素(数组下标)
                        left[i] = stack.isEmpty() ? -1 : stack.peek();
                        // 对当前遍历到的元素下标压入栈中
                        stack.push(i);
                    }
                    // 清空栈中元素
                    stack.clear();
                    // 从右到左遍历数组,每次保留栈顶元素(数组下标)
                    for (int i = n - 1; i >= 0; i--) {
                        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                            stack.pop();
                        }
                        right[i] = stack.isEmpty() ? n : stack.peek();
                        stack.push(i);
                    }
                    int maxArea = 0;
                    // 遍历数组求最大面积
                    for (int i = 0; i < n; i++) {
                        maxArea = Math.max(maxArea, (right[i] - left[i] - 1) * heights[i]);
                    }
                    return maxArea;
                }
            }
        (2)版本2:
            class Solution {
                public int largestRectangleArea(int[] heights) {
                    // 定义一个双端队列对象作为"栈"
                    Deque<Integer> stack = new ArrayDeque<>();
                    // 向栈中添加一个初始值(小于任何高度的值,作为一个标志位)
                    stack.push(-1);
                    // 定义一个变量保存最大面积
                    int maxArea = 0;
                    // 遍历数组
                    for (int i = 0; i < heights.length; ++i) {
                        // 当栈中不仅剩标志位时(即栈中添加了值且栈中添加的值未都出栈),且栈顶元素大于等于当前遍历到的值
                        // 即当前遍历到的值若添加入栈中,会破坏栈中元素对应值的单调性,所以要把大于等于的值下标都出栈
                        while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
                            // 每次出栈,当前遍历到的元素都是右边界,可以求出出栈位置到右边界的面积,每次取最大面积
                            // 由于使用单调栈,使得每个位置都能求得其到右边界的面积(即最大面积)
                            maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack.peek() - 1));
                        }   
                        stack.push(i);
                    }
                    // 以上遍历会导致栈中留下值: 一个单调栈或最后一个
                    // 需要求出剩余位置到其右边界的面积,对剩余元素出栈
                    while (stack.peek() != -1){
                        maxArea = Math.max(maxArea, heights[stack.pop()] * (heights.length - stack.peek() -1));
                    }   
                    return maxArea;
                }
            }            
    [3]复杂度分析:
        (1)时间复杂度: O(n)
        (2)空间复杂度: O(n)
4.枚举"高"+单调栈+常数优化:
    [1]思路: 在枚举"高"+单调栈的基础上,缩减一次遍历
        (1)入栈时确定左边界,出栈时确定右边界
    [2]实现:
        class Solution {
            public int largestRectangleArea(int[] heights) {
                // 数组长度
                int n = heights.length;
                int[] left = new int[n];
                int[] right = new int[n];
                // 填充right数组,保证没有下标的元素的右边界为n
                Arrays.fill(right, n);
                // 定义一个双端队列对象作为"栈"
                Deque<Integer> stack = new ArrayDeque<>();
                // 遍历数组
                for (int i = 0; i < n; i++) {
                    // 判断当前遍历到的元素与栈顶的下标对应的元素进行比较大小
                    while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                        // i即为出栈对应元素的右边界,随着遍历的继续若出现了更大的值则原来的位置的值会被覆盖
                        // 确保了各个位置的右边界是正确的
                        right[stack.peek()] = i;
                        stack.pop();
                    }
                    // 如果栈中为空,则返回-1,否则返回栈顶元素(数组下标)
                    // 栈经过上步操作,栈顶已经是左边界下标
                    left[i] = stack.isEmpty() ? -1 : stack.peek();
                    // 对当前遍历到的元素下标压入栈中
                    stack.push(i);
                }
                int maxArea = 0;
                // 遍历数组求最大面积
                for (int i = 0; i < n; i++) {
                    maxArea = Math.max(maxArea, (right[i] - left[i] - 1) * heights[i]);
                }
                return maxArea;
            }
        }
    [3]复杂度分析:
        (1)时间复杂度: O(n)
        (2)空间复杂度: O(n)