Найти область Максимун на массиве - PullRequest
Новая
       6

Найти область Максимун на массиве

0 голосов
/ 16 ноября 2018

Я делаю упражнения из приложения Структуры данных в Scala. Я кодировал вторую проблему для массивов следующим образом: 

/**
   * Given n non-negative integers a1, a2, ..., an, where each represents a
   * point at coordinate (i, ai), n vertical lines are drawn such that
   * the two endpoints of line i is at (i, ai) and (i, 0). 
   * 
   * Find two lines, which together with x-axis forms a container such
   * that the container contains the most water.
   *
   * Efficiency: O(n)
   *
   * @param a Array of line heights
   * @return Maximum area
   */
  def maxArea(a: Array[Int]): Int = {
    @tailrec
    def go(l: Int, r: Int)(max: Int): Int = {
      if (l >= r) max
      else {
        val currArea = math.min(a(l), a(r)) * (r - l)
        val area = math.max(max, currArea)
        log debug s"Current area for $l and $r is $currArea"
        log debug s"Max area till now is $area"
        if (a(l) < a(r)) go(l + 1, r)(area)
        else go(l, r - 1)(area)
      }
    }
    go(0, a.size - 1)(0)
}

Интересно, есть ли лучшая альтернативанаписать рекурсивные функции как способ циклического перебора массива, как кто-то однажды сказал мне вызывает рекурсию GOTO функционального программирования .

Вы можете проверить полный исходный кодна GitHub

Заранее спасибо.

1 Ответ

0 голосов
/ 16 ноября 2018

Вот способ реализовать ваш алгоритм без рекурсии (не то, чтобы я действительно думал, что с рекурсией что-то не так). 

def maxArea2(a: Array[Int]): Int = {
  Stream.iterate(0 -> a){ case (_, arr) =>
    if (arr.length < 2) -1 -> arr
    else {
      val (lft, rght) = (arr.head, arr.last)
      val area = (lft min rght) * (arr.length - 1)
      if (lft <= rght) area -> arr.dropWhile(_ <= lft)
      else             area -> arr.reverse.dropWhile(_ <= rght)
    }
  }.takeWhile(_._1 >= 0).maxBy(_._1)._1
}

Идея состоит в том, чтобы лениво повторять и брать (т.е. понимать) только те, которые вам нужны.

Вы заметите, что это итерирует и вычисляет области меньшее количество раз, потому что он отбрасывает значения, которые не могут превзойти текущий расчет площади.

...