【LeetCode】No.84. Largest Rectangle in Histogram -- Java Version

题目链接：https://leetcode.com/problems/largest-rectangle-in-histogram/

1. 题目介绍：

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

【Translate】： 给定一个整数数组heights，表示直方图的高，其中每个条的宽度为1，返回直方图中最大矩形的面积。

【测试用例】：

【条件约束】：

2. 题解

2.1 堆栈算局部

原题解来自于 masiwei 在 jeantimex 的 AC clean Java solution using stack 中的comment。

我个人感觉题解中比较难理解的部分就是局部最大赋值的部分。这一部分在第一个while循环中代表的是当前栈顶的元素【局部最大高】* （当前索引-栈顶弹出后的新栈顶的下标+1）【局部宽度】，以Example 1为例，如下图所示：

当索引来到元素2的位置，此时满足栈不为空，且当前元素小于栈顶元素的循环条件，partialMaxArea等于6 (6 * (4-3))；元素6作为栈顶元素被弹出，此时元素5成为了新的栈顶元素，2仍小于栈顶元素，partialMaxArea等于10 (5 * (4-2)). 所以第一个while循环中的区域最大是依次遍历找到的局部最大，而第二个while循环中的区域最大是最小高的区域最大，这个地方稍微有点绕，需要自己好好想一想，理解理解。

class Solution {
    /*
    这个题的核心是要保持一个单调递增的stack，每次遇到比栈顶小的元素，pop掉最高的元素
    此时最高的元素是局部最小的height，这里就需要利用当前i的index减去栈顶前一个元素的坐标
    这样可以得到这个局部的width是多少。这样height*width就是局部最小的面积。
    
    如果当前的i仍然大于栈顶元素，继续进行pop，这样得到下一个局部最小值
    
    最后stack剩下的height index，就是全局下最小的index，因为比他们大的，都被pop掉了
    所以直接pop stack，width就是总的len 减去他的index即可
    
    */
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0)
            return 0;
        
        Stack<Integer> stack = new Stack();
        
        int len = heights.length;
        int maxArea = Integer.MIN_VALUE;
        
        for (int i=0;i<len;i++) {
            
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int partialMaxArea = heights[stack.pop()] * (i - (stack.isEmpty()?0:stack.peek()+1));;
                maxArea = Math.max(maxArea, partialMaxArea);      
            }
            
            stack.push(i);
        }
        
        while (!stack.isEmpty()){
            int partialMaxArea = heights[stack.pop()] * (len - (stack.isEmpty()?0:stack.peek()+1));
            maxArea = Math.max(maxArea, partialMaxArea);
        }
        
        return maxArea;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

简洁写法，来自 legendaryengineer 的 Short and Clean O(n) stack based JAVA solution.

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        Stack<Integer> s = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= len; i++){
            int h = (i == len ? 0 : heights[i]);
            if (s.isEmpty() || h >= heights[s.peek()]) {
                s.push(i);
            } else {
                int tp = s.pop();
                maxArea = Math.max(maxArea, heights[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.2 辅助数据

原题解来自于 anton4 的 5ms O(n) Java solution explained (beats 96%).

（1）对于每个位置 i，我们可以通过找到其左侧和右侧的第一个位置来计算包含 i 的最大矩形的面积，其中 heights[l] < height[i] 和 heights[r ]<高度[i]; 所以 maxArea = Math.max(maxArea, heights[i] * (r - l - 1));

(2)为了找到l和r，蛮力法是从i开始做一个双向扫描；时间成本将为 O(n ^ 2)；

(3) 时间复杂度可以简化为O(n)：
例如为了离开[i]；如果高度[i - 1] < 高度[i] 则左[i] = i - 1；否则我们不需要从 i - 1 开始扫描；我们可以从 left[i - 1] 开始扫描，因为 left[i - 1] 是 i - 1 左侧的第一个高度小于 height[i - 1] 的位置，我们知道 height[i - 1] >= 高度[i]; 所以 left[i] 必须在左边或在 left[i - 1]；右侧数组类似；
由于我们不需要从头开始扫描每个 i，时间复杂度可以简化为 O(n)；

class Solution {
    public static int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current
        int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current
        lessFromRight[height.length - 1] = height.length;
        lessFromLeft[0] = -1;

        for (int i = 1; i < height.length; i++) {
            int p = i - 1;

            while (p >= 0 && height[p] >= height[i]) {
                p = lessFromLeft[p];
            }
            lessFromLeft[i] = p;
        }

        for (int i = height.length - 2; i >= 0; i--) {
            int p = i + 1;

            while (p < height.length && height[p] >= height[i]) {
                p = lessFromRight[p];
            }
            lessFromRight[i] = p;
        }

        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }

        return maxArea;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37