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.

first try: 2-d dp, maintain array dp[i][j] denotes minimal height from i to j. O(n^2), TLE.

///// dp[i][j]: minimal height between i to j: O(n^2) Time Limit Exceed ///////

public class Solution {
    public int largestRectangleArea(int[] height) {
        int n = height.length;
        if(n == 0) return 0;
        int[][] dp = new int[n][n];
        
        int max = 0;
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                int width = j - i + 1;
                if(width == 1){
                    dp[i][j] = height[i];
                }
                else{
                    dp[i][j] = Math.min(dp[i][j-1], height[j]);
                }
                max = Math.max(max, dp[i][j] * width);
            }
        }
        return max;
    }
}

second try: idea + stack.
1. For each bar, find the longest intervals containing this bar.
2. So we are using this bar as the shortest bar in the interval, otherwise, the solution could be found of that shorter bar.
3. Our task is basically seeking the first shorter bars on both left & right sides.
(bar of height 2 and bar of height 1 the following example)
4. Use stack to find the shorter bars.

(pic from GeeksForGeeks.com)

public class Solution {
    public int largestRectangleArea(int[] height) {
        if(height.length == 0) return 0;
        
        Stack left = new Stack();
        Stack right = new Stack();
        
        // width of intervals between 1st left shorter bar and 1st right shorter bar
        int[] width = new int[height.length];
        Arrays.fill(width, 1);
        
        // find the first shorter bar on the left, and save width
        for(int i = 0; i < height.length; i++){
            while(!left.isEmpty() && height[left.peek()] >= height[i]){
                left.pop();
            }
            
            // all bars on the left are taller
            if(left.isEmpty()){
                width[i] += i; 
            }
            else{
                width[i] += i - left.peek() - 1;
            }
            left.push(i);
        }
        
        // find the first shorter bar on the right, and save width
        for(int i = height.length-1; i >= 0; i--){
            while(!right.isEmpty() && height[right.peek()] >= height[i]){
                right.pop();
            }
            
            // all bars on the left are taller
            if(right.isEmpty()){
                width[i] += height.length - 1 - i; 
            }
            else{
                width[i] += right.peek() - i - 1;
            }
            right.push(i);
        }
        
        int max = 0;
        for(int i = 0; i < height.length; i++){
            max = Math.max(max, height[i] * width[i]);
        }
        return max;
    }
}