7. Largest Rectangle in Histogram

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

Approach

• The thing is we store index in our stack and not the element itself when we encounter a smaller height we just need to calculate area up until now
• we use that i == n condition because there is no index at n so that is set to zero but we can have elements in the stack still so this is more of a forcing condition for next loop
• for height we pop then we peek that is because we are trying to pick the last two tallest from stack and do the calculation
• Complexities are all n

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<>();
        int maxArea = 0, n = heights.length;
 
        for (int i = 0; i <=n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!st.isEmpty() && h < heights[st.peek()]) {
                int height = heights[st.pop()];
                int width = st.isEmpty() ? i : i - st.peek() - 1;
                maxArea = Math.max(maxArea, height*width);
            }
            st.push(i);
        }
 
        return maxArea;
    }
}