Largest rectangle in a bar chart

def largest_rectangle(heights):
    stack = []                     # indices; their heights rise from bottom to top
    best = 0
    for i, h in enumerate(heights + [0]):      # the final 0 pops everything left
        while stack and heights[stack[-1]] >= h:
            top = stack.pop()                   # i is the first bar to its right that is not taller
            left = stack[-1] + 1 if stack else 0    # and this is where it starts
            best = max(best, heights[top] * (i - left))
        stack.append(i)
    return best

#include <vector>
#include <algorithm>

long long solve(const std::vector<int>& heights) {
    const int n = static_cast<int>(heights.size());
    std::vector<int> stack;                 // indices; heights rise bottom to top
    long long best = 0;
    for (int i = 0; i <= n; ++i) {
        const int h = i == n ? 0 : heights[i];   // the final 0 pops everything
        while (!stack.empty() && heights[stack.back()] >= h) {
            const int top = stack.back();
            stack.pop_back();
            const int left = stack.empty() ? 0 : stack.back() + 1;
            best = std::max(best, 1LL * heights[top] * (i - left));
        }
        stack.push_back(i);
    }
    return best;
}

class Solution {
    public long largestRectangle(int[] heights) {
        int n = heights.length;
        int[] stack = new int[n + 1];           // indices; top is stack[top - 1]
        int top = 0;
        long best = 0;
        for (int i = 0; i <= n; i++) {
            int h = i == n ? 0 : heights[i];    // the final 0 pops everything
            while (top > 0 && heights[stack[top - 1]] >= h) {
                int bar = stack[--top];
                int left = top > 0 ? stack[top - 1] + 1 : 0;
                best = Math.max(best, (long) heights[bar] * (i - left));
            }
            stack[top++] = i;
        }
        return best;
    }
}

function largestRectangle(heights) {
  const stack = [];                  // indices; heights rise from bottom to top
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];   // the final 0 pops everything
    while (stack.length && heights[stack[stack.length - 1]] >= h) {
      const top = stack.pop();
      const left = stack.length ? stack[stack.length - 1] + 1 : 0;
      best = Math.max(best, heights[top] * (i - left));
    }
    stack.push(i);
  }
  return best;
}

fn solve(heights: &[i64]) -> i64 {
    let n = heights.len();
    let mut stack: Vec<usize> = Vec::new();     // indices; heights rise bottom to top
    let mut best = 0i64;
    for i in 0..=n {
        let h = if i == n { 0 } else { heights[i] };   // the final 0 pops everything
        while let Some(&top) = stack.last() {
            if heights[top] < h {
                break;
            }
            stack.pop();
            let left = stack.last().map_or(0, |&j| j + 1);
            best = best.max(heights[top] * (i - left) as i64);
        }
        stack.push(i);
    }
    best
}

import Data.Array

solve :: [Int] -> Int
solve hs = go 0 [] 0
  where
    n   = length hs
    arr = listArray (0, n - 1) hs
    height i = if i == n then 0 else arr ! i       -- a bar of height 0 at the end
    -- the stack is a list of indices, top at the head, heights rising towards the head
    go i stack best
      | i > n     = best
      | otherwise = case stack of
          (top : rest) | arr ! top >= height i ->
            let left = case rest of
                         (j : _) -> j + 1
                         []      -> 0
            in go i rest (max best (arr ! top * (i - left)))
          _ -> go (i + 1) (i : stack) best