Largest Rectangle in Histogram

lc84

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.

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int res = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = stack.peek();
            if (cur == -1 || (i != heights.length && heights[cur] <= heights[i])) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && stack.peek() != -1 && ( i == heights.length || heights[cur] > heights[i])){
                    int height = heights[cur];
                    stack.pop();
                    int width = i - stack.peek() - 1;
                    int area = height * width;
                    res = Math.max(res, area);
                    cur = stack.peek();
                }
                stack.push(i);
            }
        }
        return res;     
    }
}

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

        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i <= height.length; i++) {
            int curt = (i == height.length) ? -1 : height[i];
            //这里小于或者等于都能过testcase，小于等于的话就保证stack一定是个递增stackle
            while (!stack.isEmpty() && curt <= height[stack.peek()]) {
                int h = height[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }

        return max;
    }
}