LeetCode 84 - 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 .
 
Solution 1:
Brute force. O(n^2). 大きなコレクションを実行するとタイムアウトします.

public int largestRectangleArea(int[] height) {
    int n = height.length;
    int maxArea = 0;
    for(int i=0; i<n; i++) {
        int minHeight = height[i];
        for(int j=i; j<n; j++) {
            minHeight = Math.min(minHeight, height[j]);
            maxArea = Math.max(maxArea, (j-i+1)*minHeight);
        }
    }
    return maxArea;
}

 
Solution 2:
Stackで処理すると、Stack内に保存されている非減算の高さのインデックスです.

public int largestRectangleArea(int[] H) {
    int n = H.length;
    int maxArea = 0, i = 0;
    Stack<Integer> stack = new Stack<>();
    while(i <= n) {
        int h = (i == n) ? 0 : H[i];
        if(stack.isEmpty() || h >= H[stack.peek()]) {
            stack.push(i++);
        } else {
            int j = stack.pop();
            int area = (stack.isEmpty() ? i : i-1-stack.peek()) * H[j];
            maxArea = Math.max(maxArea, area);
        }
    }
    return maxArea;
}