[数据结构与算法]直方图最大矩形面积（剑指offer-39）

原题链接

题目描述

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例1

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例2

输入： heights = [2,4]
输出： 4

第1种思路（分治法）

对于某个柱子来说，最大矩形有三种情况。
1.最大矩形是以这个柱子为顶部的。
2.最大矩形的起始柱子和终点柱子都在这个柱子的左侧。
3.最大矩形的起始柱子和终点柱子都在这个柱子的右侧。

那么我们只要求出这三种情况，然后取最大值就可以了。
对于2，3来说，其实也是在分别求两边最大值，所以用递归来做就可以实现。
时间复杂度O(nlogn)

class Solution {
    public int largestRectangleArea(int[] heights) {
        return findMax(heights, 0, heights.length);
    }
    private int findMax(int[] heights, int start, int end){
        if(start == end){
            return 0;
        }
        if(start + 1 == end){
            return heights[start];
        }
        int minn = start;
        for(int i = start + 1; i < end; i++){
            if(heights[i] < heights[minn]){
                minn = i;
            }
        }
        int area = (end - start) * heights[minn];
        int left = findMax(heights, start, minn);
        int right = findMax(heights, minn + 1, end);
        return Math.max(area, Math.max(left, right));
    }
}

第2种思路（单调栈）

1. 可以建立一个单调栈，在这个栈中存放柱子的下标，而这些柱子都是递增的。
2. 那么遍历这个柱子数组，对于当前遍历到的这个柱子来说，如果它比栈顶的柱子高的话，直接压入栈顶；如果比他低的话，那么取出栈顶的柱子，然后计算以这个柱子为顶部的最大矩形面积。
3. 如果要以它为顶部（假设叫柱子t）的最大矩形面积，只需要找出离他最近的左右两个比他矮的柱子，那么最大矩形面积就是这两个矮柱子之间的柱子数量 * t的高度，因为这两个矮柱子之间别的柱子都比t要高，所以肯定要经过t的顶部。
4. 那么如何找到t左右两边的矮柱子呢？很简单，右边的柱子就是步骤2中得到的，因为遇到比栈顶柱子矮的柱子才会弹出栈顶的柱子t。那t左边的矮柱子就是弹出t之后的栈顶柱子，因为这是单调栈，所以栈中的柱子肯定都比t要矮。那么 面积 = 右柱子下标-左柱子下标 - 1
5. 还有2种特殊情况：
   1. 左侧没有比他矮的柱子了，那么就假设比他矮的柱子下标是-1呗。
   2. 右侧没有比他矮的柱子了，那么就假设比他矮的柱子下标是数组的长度呗（就是最右侧柱子的下标加1）。

因为只遍历一遍，而且每个柱子要么压要么取，所以操作单个柱子时间复杂度是O(1)，总时间复杂度是O(n)

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack();
        st.push(-1);
        int maxx = -1;
        for(int i = 0; i < heights.length; i++){
            while(st.peek() != -1 && heights[st.peek()] >= heights[i]){
                int height = heights[st.pop()];
                int width = i - st.peek() - 1;
                maxx = Math.max(maxx, height * width);
            }
            st.push(i);
        }   
        while(st.peek() != -1){
            int height = heights[st.pop()];
            int width = heights.length - st.peek() - 1;
            maxx = Math.max(maxx, height * width);
        }
        return maxx;
    }
}