pathikrit / scalgos

algorithms in scala
434 stars 129 forks source link

Make tailrec to avoid stack overflow issue? #21

Open zhaomingli007 opened 5 years ago

zhaomingli007 commented 5 years ago

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)
  }