Problem

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.

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

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

Example

Given height = [2,1,5,6,2,3],
return 10.

暴力思路

1. cycle through the array, find the farthest and larger element behind the current element and its position
2. time complexity: O(n ^ 2)

优化

1. The complexity would be O(n), because we cannot sort the array

2. we just circle through the array once to find the the firs element less than the current element both on the left and right hand side.

3. why do we need to use stack?

   1. we cycle through the array from left to right, but we need to find the first element less than current element to the left, it is a reverse order.

   2. so when we are having the ith element, the top of the stack is the nearest of the ith element.

   3. and this element should be less than the ith element

   4. otherwise pop it out of the stack, then we will find the first element that is less than the ith element

    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int[] left = new int[height.length];

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                stack.pop();
            }

            left[i] = stack.isEmpty() ? -1 : stack.peek();

            stack.push(i);
        }

        stack = new Stack<>();
        int[] right = new int[height.length];

        for (int i = height.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                stack.pop();
            }

            right[i] = stack.isEmpty() ? height.length : stack.peek();

            stack.push(i);
        }

        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < height.length; i++) {
            // System.out.println(left[i] + ": " + right[i]);
            ans = Math.max(ans, height[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }

Concise 版本

• difference:
  • 上一个版本是在push之前便要找到它左边第一个比它小和右边第一小
  • 这个版本是pop的时候同时找到它左边第一个比它小和右边第一小
  • 这个版本容易写错

    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int ans = 0;

        for (int i = 0; i <= height.length; i++) {
            int cur = (i == height.length ? -1 : height[i]);
            while (!stack.isEmpty() && height[stack.peek()] >= cur) {
                int index = stack.pop();
                int width = height[index];
                int length = stack.isEmpty() ? i : i - stack.peek() - 1;
                ans = Math.max(ans, width * length);
            }
            stack.push(i);
        }

        return ans;
    }