Largest Rectangle in Histogram — Monotonic Increasing Stack

# Python — one-pass with sentinel
def largestRectangleArea(heights):
    heights = [0] + heights + [0]  # sentinels
    stack = [0]; ans = 0
    for i in range(1, len(heights)):
        while heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1
            ans = max(ans, h*w)
        stack.append(i)
    return ans

// Java
public int largestRectangleArea(int[] heights) {
    int n=heights.length; int ans=0;
    Deque<Integer> stack=new ArrayDeque<>();
    for (int i=0;i<=n;i++) {
        int h=(i==n)?0:heights[i];
        while (!stack.isEmpty()&&heights[stack.peek()]>h) {
            int height=heights[stack.pop()];
            int width=stack.isEmpty()?i:i-stack.peek()-1;
            ans=Math.max(ans,height*width);
        }
        stack.push(i);
    }
    return ans;
}

// C++
int largestRectangleArea(vector<int>& heights) {
    heights.push_back(0); stack<int> st; int ans=0;
    for (int i=0;i<(int)heights.size();i++) {
        while (!st.empty()&&heights[st.top()]>heights[i]) {
            int h=heights[st.top()]; st.pop();
            int w=st.empty()?i:i-st.top()-1;
            ans=max(ans,h*w);
        }
        st.push(i);
    }
    return ans;
}