scalgos
scalgos copied to clipboard
Make tailrec to avoid stack overflow issue?
https://github.com/pathikrit/scalgos/blob/9e99f73b4241f42cc40a1fd890e72dbeda2df54f/src/main/scala/com/github/pathikrit/scalgos/Greedy.scala#L15
def maxRectangleInHistogram(heights: List[Int]): Int = {
@tailrec def solve(stack: List[(Int, Int)], remaining: List[(Int, Int)],maxArea:Int): Int = {
def area(x: Int, y: Int) = (heights.length - remaining.length - x) * y
(stack, remaining) match {
case ( Nil, Nil) => maxArea
case ((y, x) :: rest, Nil) => solve( rest, Nil, maxArea max area(x, y))
case ((y, x) :: rest, (h, i) :: hs) if h <= y => solve( rest, (h, x) :: hs, maxArea max area(x, y))
case ( _, block :: hs) => solve(block :: stack, hs, maxArea)
}
}
solve(Nil, heights.zipWithIndex,0)
}