61 lines
1.9 KiB
Go
61 lines
1.9 KiB
Go
package largest_rectangle_in_histogram
|
|
|
|
type Box struct {
|
|
Start int
|
|
Height int
|
|
}
|
|
|
|
// Calculates the size of the box, from its starting point upto (and NOT
|
|
// including) a certain point.
|
|
func (b Box) Size(upto int) int {
|
|
return (upto - b.Start) * b.Height
|
|
}
|
|
|
|
func LargestRectangleArea(heights []int) int {
|
|
// This is a stack, containing all boxes that haven't been completed yet. Each
|
|
// box contains two integers. The first is the starting index, and the second
|
|
// is the height of the box.
|
|
boxes := []Box{}
|
|
// The accumulation of the biggest box so far.
|
|
biggest := 0
|
|
// Add a number that is guaranted to be lower than any other. This will pop out
|
|
// any boxes left in the stack at the end of the program.
|
|
heights = append(heights, -1)
|
|
|
|
for i, height := range heights {
|
|
// This is the farthest index back where the eventual new box can start.
|
|
// Everytime we pop a box off the top of the stack, this means every item
|
|
// from the start of the box until now is > the current height. So, we can
|
|
// extend that box at least that far back.
|
|
farthest := i
|
|
|
|
for len(boxes) > 0 {
|
|
top := boxes[len(boxes)-1]
|
|
|
|
// The boxes are implicitly ordered by height. When one gets the top box,
|
|
// all below must have a <= height.
|
|
//
|
|
// If the very top box has a height <= to the current height, that means
|
|
// all boxes left will carry over into the next iteration, so we can continue.
|
|
if top.Height < height {
|
|
break
|
|
}
|
|
|
|
// Since this box is taller than the current height, it ends here.
|
|
// We calculate its size, and accumulate it in the `biggest` variable.
|
|
biggest = max(biggest, top.Size(i))
|
|
|
|
// Remove it from the stack.
|
|
boxes = boxes[:len(boxes)-1]
|
|
|
|
// Push the starting point of the box farther back.
|
|
farthest = top.Start
|
|
}
|
|
|
|
// A box is always created for each new height.
|
|
boxes = append(boxes, Box{Start: farthest, Height: height})
|
|
}
|
|
|
|
return biggest
|
|
}
|