15.3 Задача о максимальной вместимости¶

Question

Дан массив \(ht\), где каждый элемент обозначает высоту вертикальной перегородки. Любые две перегородки в массиве вместе с пространством между ними образуют контейнер.

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

Требуется выбрать две перегородки так, чтобы образованный ими контейнер имел максимальную вместимость. Пример показан на рисунке 15-7.

Пример данных для задачи о максимальной вместимости

Рисунок 15-7 Пример данных для задачи о максимальной вместимости

Контейнер образуется произвольными двумя перегородками, поэтому состоянием задачи служит пара индексов этих перегородок, обозначим ее как \([i, j]\).

Согласно условию, вместимость равна произведению высоты на ширину, где высота определяется короткой перегородкой, а ширина - разностью индексов двух перегородок. Обозначим вместимость через \(cap[i, j]\), тогда формула принимает вид:

\[ cap[i, j] = \min(ht[i], ht[j]) \times (j - i) \]

Пусть длина массива равна \(n\). Тогда число пар перегородок, то есть общее число состояний, равно \(C_n^2 = \frac{n(n - 1)}{2}\). Самый прямолинейный подход - перебрать все состояния, после чего найти максимальную вместимость. Его временная сложность равна \(O(n^2)\).

1. Определение жадной стратегии¶

У этой задачи есть и более эффективное решение. Как показано на рисунке 15-8, рассмотрим состояние \([i, j]\), где индексы удовлетворяют \(i < j\), а высоты - условию \(ht[i] < ht[j]\), то есть \(i\) - короткая перегородка, а \(j\) - длинная.

Начальное состояние

Рисунок 15-8 Начальное состояние

Как показано на рисунке 15-9, если в этот момент сдвинуть длинную перегородку \(j\) ближе к короткой перегородке \(i\), то вместимость обязательно уменьшится.

Причина в том, что после смещения длинной перегородки \(j\) ширина \(j-i\) обязательно станет меньше, а высота определяется короткой перегородкой, поэтому высота либо останется прежней (если \(i\) останется короткой перегородкой), либо уменьшится (если сдвинутая \(j\) станет короткой перегородкой).

Состояние после перемещения длинной перегородки внутрь

Рисунок 15-9 Состояние после перемещения длинной перегородки внутрь

Рассуждая в обратную сторону, только сдвигая короткую перегородку \(i\) внутрь, мы можем получить шанс увеличить вместимость. Хотя ширина при этом обязательно уменьшится, высота может возрасти (если после перемещения короткая перегородка \(i\) станет выше). Например, на рисунке 15-10 после перемещения короткой перегородки площадь увеличивается.

Состояние после перемещения короткой перегородки внутрь

Рисунок 15-10 Состояние после перемещения короткой перегородки внутрь

Отсюда и выводится жадная стратегия для этой задачи: инициализировать два указателя по краям контейнера и на каждом шаге сдвигать внутрь указатель, соответствующий короткой перегородке, пока указатели не встретятся.

На рисунках ниже показан процесс выполнения этой жадной стратегии.

В начальном состоянии указатели \(i\) и \(j\) стоят на двух концах массива.
Вычислить вместимость текущего состояния \(cap[i, j]\) и обновить максимальную вместимость.
Сравнить высоты перегородок \(i\) и \(j\), после чего сдвинуть короткую перегородку на одну позицию внутрь.
Повторять шаги 2. и 3. до тех пор, пока \(i\) и \(j\) не встретятся.

Рисунок 15-11 Жадный процесс решения задачи о максимальной вместимости

2. Код реализации¶

Цикл в коде выполняется не более \(n\) раз, поэтому временная сложность равна \(O(n)\).

Переменные \(i\), \(j\), \(res\) используют дополнительную память постоянного размера, поэтому пространственная сложность равна \(O(1)\).

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

max_capacity.py

def max_capacity(ht: list[int]) -> int:
    """Максимальная вместимость: жадный алгоритм"""
    # Инициализировать i и j так, чтобы они располагались по двум концам массива
    i, j = 0, len(ht) - 1
    # Начальная максимальная вместимость равна 0
    res = 0
    # Выполнять жадный выбор в цикле, пока две доски не встретятся
    while i < j:
        # Обновить максимальную вместимость
        cap = min(ht[i], ht[j]) * (j - i)
        res = max(res, cap)
        # Сдвигать внутрь более короткую сторону
        if ht[i] < ht[j]:
            i += 1
        else:
            j -= 1
    return res

max_capacity.cpp

/* Максимальная вместимость: жадный алгоритм */
int maxCapacity(vector<int> &ht) {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    int i = 0, j = ht.size() - 1;
    // Начальная максимальная вместимость равна 0
    int res = 0;
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while (i < j) {
        // Обновить максимальную вместимость
        int cap = min(ht[i], ht[j]) * (j - i);
        res = max(res, cap);
        // Сдвигать внутрь более короткую сторону
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.java

/* Максимальная вместимость: жадный алгоритм */
int maxCapacity(int[] ht) {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    int i = 0, j = ht.length - 1;
    // Начальная максимальная вместимость равна 0
    int res = 0;
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while (i < j) {
        // Обновить максимальную вместимость
        int cap = Math.min(ht[i], ht[j]) * (j - i);
        res = Math.max(res, cap);
        // Сдвигать внутрь более короткую сторону
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.cs

/* Максимальная вместимость: жадный алгоритм */
int MaxCapacity(int[] ht) {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    int i = 0, j = ht.Length - 1;
    // Начальная максимальная вместимость равна 0
    int res = 0;
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while (i < j) {
        // Обновить максимальную вместимость
        int cap = Math.Min(ht[i], ht[j]) * (j - i);
        res = Math.Max(res, cap);
        // Сдвигать внутрь более короткую сторону
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.go

/* Максимальная вместимость: жадный алгоритм */
func maxCapacity(ht []int) int {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    i, j := 0, len(ht)-1
    // Начальная максимальная вместимость равна 0
    res := 0
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    for i < j {
        // Обновить максимальную вместимость
        capacity := int(math.Min(float64(ht[i]), float64(ht[j]))) * (j - i)
        res = int(math.Max(float64(res), float64(capacity)))
        // Сдвигать внутрь более короткую сторону
        if ht[i] < ht[j] {
            i++
        } else {
            j--
        }
    }
    return res
}

max_capacity.swift

/* Максимальная вместимость: жадный алгоритм */
func maxCapacity(ht: [Int]) -> Int {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    var i = ht.startIndex, j = ht.endIndex - 1
    // Начальная максимальная вместимость равна 0
    var res = 0
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while i < j {
        // Обновить максимальную вместимость
        let cap = min(ht[i], ht[j]) * (j - i)
        res = max(res, cap)
        // Сдвигать внутрь более короткую сторону
        if ht[i] < ht[j] {
            i += 1
        } else {
            j -= 1
        }
    }
    return res
}

max_capacity.js

/* Максимальная вместимость: жадный алгоритм */
function maxCapacity(ht) {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    let i = 0,
        j = ht.length - 1;
    // Начальная максимальная вместимость равна 0
    let res = 0;
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while (i < j) {
        // Обновить максимальную вместимость
        const cap = Math.min(ht[i], ht[j]) * (j - i);
        res = Math.max(res, cap);
        // Сдвигать внутрь более короткую сторону
        if (ht[i] < ht[j]) {
            i += 1;
        } else {
            j -= 1;
        }
    }
    return res;
}

max_capacity.ts

/* Максимальная вместимость: жадный алгоритм */
function maxCapacity(ht: number[]): number {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    let i = 0,
        j = ht.length - 1;
    // Начальная максимальная вместимость равна 0
    let res = 0;
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while (i < j) {
        // Обновить максимальную вместимость
        const cap: number = Math.min(ht[i], ht[j]) * (j - i);
        res = Math.max(res, cap);
        // Сдвигать внутрь более короткую сторону
        if (ht[i] < ht[j]) {
            i += 1;
        } else {
            j -= 1;
        }
    }
    return res;
}

max_capacity.dart

/* Максимальная вместимость: жадный алгоритм */
int maxCapacity(List<int> ht) {
  // Инициализировать i и j так, чтобы они располагались по двум концам массива
  int i = 0, j = ht.length - 1;
  // Начальная максимальная вместимость равна 0
  int res = 0;
  // Выполнять жадный выбор в цикле, пока две доски не встретятся
  while (i < j) {
    // Обновить максимальную вместимость
    int cap = min(ht[i], ht[j]) * (j - i);
    res = max(res, cap);
    // Сдвигать внутрь более короткую сторону
    if (ht[i] < ht[j]) {
      i++;
    } else {
      j--;
    }
  }
  return res;
}

max_capacity.rs

/* Максимальная вместимость: жадный алгоритм */
fn max_capacity(ht: &[i32]) -> i32 {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    let mut i = 0;
    let mut j = ht.len() - 1;
    // Начальная максимальная вместимость равна 0
    let mut res = 0;
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while i < j {
        // Обновить максимальную вместимость
        let cap = std::cmp::min(ht[i], ht[j]) * (j - i) as i32;
        res = std::cmp::max(res, cap);
        // Сдвигать внутрь более короткую сторону
        if ht[i] < ht[j] {
            i += 1;
        } else {
            j -= 1;
        }
    }
    res
}

max_capacity.c

/* Максимальная вместимость: жадный алгоритм */
int maxCapacity(int ht[], int htLength) {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    int i = 0;
    int j = htLength - 1;
    // Начальная максимальная вместимость равна 0
    int res = 0;
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while (i < j) {
        // Обновить максимальную вместимость
        int capacity = myMin(ht[i], ht[j]) * (j - i);
        res = myMax(res, capacity);
        // Сдвигать внутрь более короткую сторону
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.kt

/* Максимальная вместимость: жадный алгоритм */
fun maxCapacity(ht: IntArray): Int {
    // Инициализировать i и j так, чтобы они располагались по двум концам массива
    var i = 0
    var j = ht.size - 1
    // Начальная максимальная вместимость равна 0
    var res = 0
    // Выполнять жадный выбор в цикле, пока две доски не встретятся
    while (i < j) {
        // Обновить максимальную вместимость
        val cap = min(ht[i], ht[j]) * (j - i)
        res = max(res, cap)
        // Сдвигать внутрь более короткую сторону
        if (ht[i] < ht[j]) {
            i++
        } else {
            j--
        }
    }
    return res
}

max_capacity.rb

### Максимальная вместимость: жадный алгоритм ###
def max_capacity(ht)
  # Инициализировать i и j так, чтобы они располагались по двум концам массива
  i, j = 0, ht.length - 1
  # Начальная максимальная вместимость равна 0
  res = 0

  # Выполнять жадный выбор в цикле, пока две доски не встретятся
  while i < j
    # Обновить максимальную вместимость
    cap = [ht[i], ht[j]].min * (j - i)
    res = [res, cap].max
    # Сдвигать внутрь более короткую сторону
    if ht[i] < ht[j]
      i += 1
    else
      j -= 1
    end
  end

  res
end

Визуализация кода

Во весь экран >

3. Доказательство корректности¶

Жадный алгоритм быстрее полного перебора именно потому, что каждый жадный шаг «пропускает» часть состояний.

Например, в состоянии \(cap[i, j]\) перегородка \(i\) является короткой, а \(j\) - длинной. Если жадно сдвинуть короткую перегородку \(i\) на одну позицию внутрь, то состояния, показанные на рисунке 15-12, будут «пропущены». Это означает, что позже мы уже не сможем проверить вместимость этих состояний.

\[ cap[i, i+1], cap[i, i+2], \dots, cap[i, j-2], cap[i, j-1] \]

Состояния, пропущенные из-за смещения короткой перегородки

Рисунок 15-12 Состояния, пропущенные из-за смещения короткой перегородки

Нетрудно заметить, что эти пропущенные состояния на самом деле и есть все состояния, в которых длинная перегородка \(j\) сдвигается внутрь. Ранее мы уже доказали, что перемещение длинной перегородки внутрь обязательно уменьшает вместимость. Иными словами, пропущенные состояния не могут быть оптимальным решением, поэтому их пропуск не приводит к потере оптимума.

Приведенный анализ показывает, что операция перемещения короткой перегородки является «безопасной», а жадная стратегия действительно эффективна.

15.3 Задача о максимальной вместимости¶

1. Определение жадной стратегии¶

2. Код реализации¶

3. Доказательство корректности¶

Оставляйте свои идеи, вопросы и предложения в комментариях