84. Largest rectangle histogram

#include <stdlib.h>

int largestRectangleArea(int *heights, int n) {
    int *st = malloc(n * sizeof(int)); // indices of increasing heights
    int top = 0, best = 0;

    for (int i = 0; i <= n; i++) {
        int h = i < n ? heights[i] : 0; // sentinel flushes the stack
        while (top > 0 && heights[st[top - 1]] > h) {
            int height = heights[st[--top]];
            int prev = top ? st[top - 1] : -1;
            int area = height * (i - prev - 1);
            if (area > best)
                best = area;
        }
        st[top++] = i;
    }
    free(st);
    return best;
}

#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
  int largestRectangleArea(vector<int> &heights) {
    int maxArea = 0;
    stack<int> st;

    for (int i = 0; i < heights.size(); i++) {
      while (!st.empty() && heights[st.top()] > heights[i]) {
        int idx = st.top();
        st.pop();

        int prev = st.empty() ? -1 : st.top();
        int width = (i - 1) - (prev + 1) + 1;
        int newArea = heights[idx] * width;
        maxArea = max(maxArea, newArea);
      }
      st.push(i);
    }

    while (!st.empty()) {
      int idx = st.top();
      st.pop();
      int prev = st.empty() ? -1 : st.top();
      int newArea = heights[idx] * (heights.size() - prev - 1);
      maxArea = max(maxArea, newArea);
    }

    return maxArea;
  }
};

package main

func largestRectangleArea(heights []int) int {
    st := []int{} // indices of increasing heights
    best := 0

    for i := 0; i <= len(heights); i++ {
        h := 0 // sentinel flushes the stack
        if i < len(heights) {
            h = heights[i]
        }
        for len(st) > 0 && heights[st[len(st)-1]] > h {
            height := heights[st[len(st)-1]]
            st = st[:len(st)-1]
            prev := -1
            if len(st) > 0 {
                prev = st[len(st)-1]
            }
            best = max(best, height*(i-prev-1))
        }
        st = append(st, i)
    }
    return best
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length, best = 0;
        Deque<Integer> st = new ArrayDeque<>(); // indices of increasing heights

        for (int i = 0; i <= n; i++) {
            int h = i < n ? heights[i] : 0; // sentinel flushes the stack
            while (!st.isEmpty() && heights[st.peek()] > h) {
                int height = heights[st.pop()];
                int prev = st.isEmpty() ? -1 : st.peek();
                best = Math.max(best, height * (i - prev - 1));
            }
            st.push(i);
        }
        return best;
    }
}

class Solution {
  largestRectangleArea(heights) {
    const n = heights.length;
    const st = []; // indices of increasing heights
    let best = 0;

    for (let i = 0; i <= n; i++) {
      const h = i < n ? heights[i] : 0; // sentinel flushes the stack
      while (st.length && heights[st[st.length - 1]] > h) {
        const height = heights[st.pop()];
        const prev = st.length ? st[st.length - 1] : -1;
        best = Math.max(best, height * (i - prev - 1));
      }
      st.push(i);
    }
    return best;
  }
}

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        st = []  # indices of increasing heights
        best = 0

        for i in range(n + 1):
            h = heights[i] if i < n else 0  # sentinel flushes the stack
            while st and heights[st[-1]] > h:
                height = heights[st.pop()]
                prev = st[-1] if st else -1
                best = max(best, height * (i - prev - 1))
            st.append(i)
        return best

struct Solution;

impl Solution {
    fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let n = heights.len();
        let mut st: Vec<usize> = Vec::new(); // indices of increasing heights
        let mut best = 0;

        for i in 0..=n {
            let h = if i < n { heights[i] } else { 0 }; // sentinel flushes the stack
            while let Some(&top) = st.last() {
                if heights[top] <= h {
                    break;
                }
                st.pop();
                let prev = st.last().map_or(-1, |&p| p as i32);
                best = best.max(heights[top] * (i as i32 - prev - 1));
            }
            st.push(i);
        }
        best
    }
}