スタックで棒グラフの中に入るいちばん大きい長方形を求める

def largest_rect(heights):
    hs = heights + [0]
    stack = []
    best = 0
    for i in range(len(hs)):
        h = hs[i]
        while stack:
            top = stack[-1]
            if hs[top] <= h:
                break
            stack.pop()
            left = -1
            if stack:
                left = stack[-1]
            w = i - left - 1
            area = hs[top] * w
            if area > best:
                best = area
        stack.append(i)
    return best

function largestRect(
  heights
) {
  const hs = [...heights, 0];
  const n = hs.length;
  const stack = [];
  let best = 0;
  for (let i = 0; i < n; i++) {
    const h = hs[i];
    while (stack.length > 0) {
      const top = stack.at(-1);
      if (hs[top] <= h) break;
      stack.pop();
      const left =
        stack.length > 0
          ? stack.at(-1)
          : -1;
      const w = i - left - 1;
      const area = hs[top] * w;
      if (area > best) {
        best = area;
      }
    }
    stack.push(i);
  }
  return best;
}

func largestRect(
	heights []int,
) int {
	n := len(heights)
	hs := make([]int, n+1)
	copy(hs, heights)
	stack := []int{}
	best := 0
	for i, h := range hs {
		for len(stack) > 0 {
			k := len(stack) - 1
			top := stack[k]
			if hs[top] <= h {
				break
			}
			stack = stack[:k]
			left := -1
			if k > 0 {
				left = stack[k-1]
			}
			w := i - left - 1
			area := hs[top] * w
			best = max(best, area)
		}
		stack = append(stack, i)
	}
	return best
}