package main

func largestRectangleAreaSlow(heights []int) (area int) {
	n := len(heights)
	if n == 0 {
		return
	}
	for i := 0; i < n; i++ {
		min := heights[i]
		for j := i; j < n; j++ {
			if heights[j] < min {
				min = heights[j]
			}
			if (j-i+1)*min > area {
				area = (j - i + 1) * min
			}
		}
	}
	return
}

func largestRectangleArea(heights []int) (maxArea int) {
	st := make([]int, 0) // The max area must be between two smaller bar
	i, l, n := 0, 0, len(heights)
	for i < n {
		if l == 0 || heights[i] >= heights[st[l-1]] {
			st = append(st, i)
			i, l = i+1, l+1
		} else {
			t := st[l-1]
			st = st[:l-1]
			l--
			var area int
			if l == 0 {
				area = heights[t] * i
			} else {
				area = heights[t] * (i - st[l-1] - 1)
			}
			if area > maxArea {
				maxArea = area
			}
		}
	}
	for l != 0 {
		t := st[l-1]
		st = st[:l-1]
		l--
		var area int
		if l == 0 {
			area = heights[t] * i
		} else {
			area = heights[t] * (i - st[l-1] - 1)
		}
		if area > maxArea {
			maxArea = area
		}
	}
	return
}

// func main() {
// 	h := []int{2, 1, 5, 6, 2, 3}
// 	println(largestRectangleArea(h))
// 	h = []int{}
// 	println(largestRectangleArea(h))
// }