Leetcode: Largest Rectangle in Histogram

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 = 10 unit.

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

Understand the problem:
A histogram problem very similar to container with most water and trapping rain water problems. So the first thing is to come out the area of the histograms, which could be calculated as area = (j - i + 1) * min(A[i], A[j]). Thus the most straight-forward way is to try each pair of i and j, and get its area, as well as its largest area. 

A wrong Solution:
As described above, the most straight-forward way is to iterate through all possible i and j, and calculate the area. So the time complexity is O(n^2) for this solution. 

Code (Java):

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = 0; j < height.length; j++) {
                int area = (j - i + 1) * Math.min(height[i], height[j]);
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        
        return maxArea;
    }
}

The height = [2,1,5,6,2,3], generated the result of 12, instead of 10. The reason is because the area calculation equation was wrong. For a pair of i, j, its area is not determined by the min (A[i], A[j])., but minimum A[k], i <= i <= j.  

The correct Solution:

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            int minV = height[i];
            for (int j = i; j < height.length; j++) {
              minV = Math.min(minV, height[j]);  
              int area = (j - i + 1) * minV;
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        
        return maxArea;
    }
}

A better Solution:

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        if (height.length == 1) {
            return height[0];
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        int[] copy = new int[height.length + 1];
        copy = Arrays.copyOf(height, height.length + 1);
        
        int maxArea = 0;
        int i = 0;
        
        while (i < copy.length) {
            if (stack.isEmpty() || copy[i] > copy[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int index = stack.pop();
                int localArea = copy[index] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, localArea);
            }
        }
        
        return maxArea;
    }
}