0084. Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram

Description

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

**Input:** heights = [2,1,5,6,2,3]
**Output:** 10
**Explanation:** The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

**Input:** heights = [2,4]
**Output:** 4

Constraints:

• 1 <= heights.length <= 105

• 0 <= heights[i] <= 104

ac1: stack

stack & array push -1 at first, like #32 push 0 at last, like this one #84

class Solution {
    public int largestRectangleArea(int[] heights) {
        // edge cases
        if (heights.length == 0) return 0;

        int max = 0;
        // stack iterate
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(-1);
        for (int i = 0; i <= heights.length; i++) {
            int currh = i == heights.length ? 0 : heights[i];
            while (stack.peek() != -1 && currh < heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int w = i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }

        return max;
    }
}

/*
stack
push -1 at first, like #32
push 0 at last, like this one #84

if stack.isEmpty() -> stack.peek() != -1 || heights[i] >= height[stack.peek()], push
while height[i] < height[stack.peek()], h = height[stack.pop()], w = i - stack.peek() - 1

*/

This is more intuitive without pushing -1 or 0:

class Solution {
    public int largestRectangleArea(int[] heights) {
        // edge cases
        if (heights.length == 0) return 0;
        
        int len = heights.length;
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            int h = heights[stack.pop()];
            int w = stack.isEmpty() ? len : len - stack.peek() - 1;
            max = Math.max(max, h * w);
        }
        
        return max;
    }
}