1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int length = heights.length;
        for (int i = 0; i < length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

Brute force.把所有bar构成的pair走一遍,求bar构成的pair表示左右两个边界.从(0,0)开始,然后是(0,1),(0,2)…(0,heights.length-1),走的过程中始终维护着一个变量来记录目前遇到的最小height是多少.这样就不用确定pair后在遍历pair确定的范围内的最小值了.

时间复杂度:O(n^2)空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> monoStack = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!monoStack.isEmpty() && heights[i] < heights[monoStack.peek()]) {
                int currMinHeightIdx = monoStack.pop();
                int prevSmallerIdx = monoStack.isEmpty() ? -1 : monoStack.peek();
                maxArea = Math.max(maxArea, (i - prevSmallerIdx - 1) * heights[currMinHeightIdx]);
            }
            monoStack.push(i);
        }
        while (!monoStack.isEmpty()) {
            int currMinHeightIdx = monoStack.pop();
            int prevSmallerIdx = monoStack.isEmpty() ? -1 : monoStack.peek();
            maxArea = Math.max(maxArea, (heights.length - prevSmallerIdx - 1) * heights[currMinHeightIdx]);
        }
        return maxArea;
    }
}

这道题的关键就是让每个bar都试一下成为minimum,也就是如果某个bar比方说height[i]这个bar, 它是某个rectangle的minimum的话,那么这样的rectangle最大能够多大?此时我们需要知道height[i]的previous smaller以及next smaller, 因为超过这两个边界, 构成的rectangle中heights[i]就不是minimum了. 那这不正是monostack干的事情: 在一个位置, monostack能告诉我们该位置数字的previous smaller, 同时被pop的出来的数字知道自己的next smaller是谁.如果一个数字被pop出来,那么它就满足做minimum的条件了, 我们就可以求该数对应的height做minimu的时候, 最大的rectangle是多少了. 因为此时的heights[i]是它的next smaller, 而栈里如果有数字的话, 那这个数字就是它的previous smaller的index, 如果栈为空, 就说明没有比它小的数字, 那么可以认为左侧都比它大. 此时构成的rectangle的高就是heights[stack.pop()], stack.pop()表示那个要被pop出来的数字, rectangle的长就是i - (previous smaller idx or -1) - 1. 这是因为i和previous smaller idx都不算在这个rectangle里面因为它们都比heights[stack.pop()]小, 我们要的是让heights[stack.pop()]作为rectangle的minimum. 由于我们计算时左右的边界都是exclusive的, 因此是right - left - 1. 为了保证这个逻辑统一, 当stack是空的时候, 我们人为让left == -1, 也就是index 0左侧一个位置, 这样right和left框起来的区域就是长, 并且不包含left和right.

总结一句话就是让每个bar都作为minimum, 看这样它们能组成的rectangle的area最大是多少. 之所以这样能得到答案是是因为最终的答案对应的那种截取情况, 一定有一个bar或某几个bar最小, 那么如果我们知道每个bar当它作为minimum时能得到的最大rectangle area的时候, 我们就能得到全局最大的area.

时间复杂度: O(n)
空间复杂度: O(n)