[LeetCode 84] Largest Rectangle

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

image

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]

image

The largest rectangle is shown in the shaded area, which has area = 10 unit

Example:

**Input:** [2,1,5,6,2,3]
**Output:** 10

Solution

1. 参考链接 https://www.cnblogs.com/grandyang/p/4322653.html](https://www.cnblogs.com/grandyang/p/4322653.html)
2. 用Stack来做的方法其实和O(n2)的方法有异曲同工之妙，只是用递增栈来实现线性扫描，每个数字只需要入栈一次，并处理一次即可。
   • 在给定的数组最后追加一个0，这样可以处理最后一位。
   • 如果栈为空，或者当前高度比栈顶的高度大，则推入当前的Index （不是高度！！，需要index来计算宽度）
   • 如果当前高度比栈顶的高度小，则触发计算最大面积。
     • 面积 = height * Width，
     • 因为当前高度更小，所以弹出栈顶，那么高度 = 栈顶弹出的index所在的高度，宽度为1， 求出size，更新maxSize。
     • 再次比较当前高度和栈顶高度，如果当前高度还是更小，那么继续弹出栈顶，那么此时宽度为2 ，求出size，更新maxSize 。。。。重复直到当前高度比栈顶大， 推入当前Index
     • 总结起来，在不断弹出栈顶计算面积时，宽度 = currentIndex - stack.peek () - 1
     • 特殊情况，当前栈为空了，说明此时的高度是全部里面最小的，那么宽度就是整个数组的长度。

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0)
            return 0;
        
        int[] newHeights = Arrays.copyOfRange (heights, 0, heights.length + 1);
        Stack<Integer> tracker = new Stack<> ();
        int maxSize = 0;
        
        for (int i = 0; i < newHeights.length; i++) {
            if (tracker.isEmpty () || newHeights [i] >= newHeights[tracker.peek ()]) {
                tracker.push (i);
            } else {
                while (!tracker.isEmpty () && newHeights [i] < newHeights[tracker.peek ()]) {
                    int currentHighestIndex = tracker.pop ();
                    int currentSize = newHeights [currentHighestIndex] * (tracker.isEmpty () ? i : i - tracker.peek () - 1);
                    maxSize = Math.max (maxSize, currentSize);
                }
                tracker.push (i);
            }
        }
        
        return maxSize;
    }
}