跳转至

15.3   最大容量问题

Question

输入一个数组 \(ht\) ,其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板,以及它们之间的空间可以组成一个容器。

容器的容量等于高度和宽度的乘积(面积),其中高度由较短的隔板决定,宽度是两个隔板的数组索引之差。

请在数组中选择两个隔板,使得组成的容器的容量最大,返回最大容量。示例如图 15-7 所示。

图 15-7   最大容量问题的示例数据

图解 15-7:两根隔板的最大容量

选择两根隔板组成容器,容量由较短隔板的高度与两板间距的乘积决定,目标是找到容量最大的组合。

最大容量问题给定长度为 8 的垂直隔板高度数组 ht = [3, 8, 5, 2, 7, 7, 3, 4](索引 0 至 7)。任选两根隔板 [i, j] 围成容器时,容器宽度为两板索引之差 j - i,盛水高度由两板中较短的那根决定(即 min(ht[i], ht[j]),中间隔板不会阻挡或缩减该定义下的盛水面积)。

画面纵轴标示隔板高度 0 至 8,横轴标示数组索引 0 至 7,各索引位置立有对应高度的柱状隔板。其中索引 1(高 8)和索引 5(高 7)两根隔板及底部横轴区间被深色高亮,两板之间高为 7、宽为 4 的矩形盛水区域以浅蓝色半透明填充,左侧纵轴高度 7 处以蓝紫色“短板”文字和水平虚线标出水位上限。图底标注“最大容量为 (5 - 1) × 7 = 28”。

水位由右侧高度 7 的较短隔板限制,两板间距是 5 - 1 = 4,故面积为 4 × 7 = 28。“短板”文字标在纵轴高度 7 旁,指向这一水位,并不是标在索引 5 上方。此图展示最大值及对应组合,其他组合的排除过程见后文。

容器由任意两个隔板围成,因此本题的状态为两个隔板的索引,记为 \([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-8:容器双指针的初始状态

展示左右两端的初始容器,作为比较移动长板与移动短板的基准。

为探究双指针贪心策略的移动方向,对同一高度数组 ht = [3, 8, 5, 2, 7, 7, 3, 4] 考察两指针分别位于左右两端的初始状态 [i, j] = [0, 7],用作后续比较“向内移动长板”与“向内移动短板”的基准。

画面索引 0 的隔板上方标有左指针 i,对应隔板高度 ht[0] = 3;索引 7 的隔板上方标有右指针 j,对应隔板高度 ht[7] = 4。两端的隔板高亮,横跨索引 0 至 7、高度齐平左端短板 3 的浅蓝色矩形表示当前盛水区域,图下方标注“i 为短板,j 为长板”,并写出当前容量 cap = min(3, 4) × (7 - 0) = 21。

因为左板 3 短于右板 4,水高只能达到 3;两板间距为 7,所以容量为 21。这只是搜索起点的当前容量,不是全数组最大值。

如图 15-9 所示,若此时将长板 \(j\) 向短板 \(i\) 靠近,则容量一定变小。

这是因为在移动长板 \(j\) 后,宽度 \(j-i\) 肯定变小;而高度由短板决定,因此高度只可能不变( \(i\) 仍为短板)或变小(移动后的 \(j\) 成为短板)。

图 15-9   向内移动长板后的状态

图解 15-9:容器向内移动长板

保持短板不动而内移另一端,会缩短宽度且无法抬高水位上限,因此容量不能增大。

高度数组为 ht = [3, 8, 5, 2, 7, 7, 3, 4]。初始状态 i = 0(短板高 3)、j = 7(长板高 4),容量为 21。本图在保持左端短板不动的前提下,将右端长板向内移动一格,考察这一局部操作为何不能改善当前容量。

画面中左指针仍停在 i = 0(高度 3),右指针由索引 7 向左移动一格至 j = 6(高度 ht[6] = 3,原索引 7 的隔板变回普通未选中灰柱)。浅蓝色盛水区域随之缩窄为横跨索引 0 至 6、高度为 3 的矩形,图下方标注“向内移动长板,容量一定减小”,并写出 cap = min(3, 3) × (6 - 0) = 18。

右端由高 4 变为高 3,水位仍为 min(3, 3) = 3,而宽度由 7 缩至 6,因此容量从 21 降到 18。这个 18 只是移动长板后的局部比较值。

进一步按这一性质推论:固定短板 i = 0,无论把 j 改为索引 1 至 6 中哪一个,水高都不会超过 3,宽度却更小,所以这些组合都不能改善原来的 21。图只画出 j = 6 的一例,其余组合是据此推断;贪心搜索可以排除这些仍保留 i = 0 的状态,转而移动短板 i。

反向思考,我们只有向内收缩短板 \(i\) ,才有可能使容量变大。因为虽然宽度一定变小,但高度可能会变大(移动后的短板 \(i\) 可能会变长)。例如在图 15-10 中,移动短板后面积变大。

图 15-10   向内移动短板后的状态

图解 15-10:容器向内移动短板

向内移动短板可能提高容器高度,从而增大容量;本例容量从 21 增至 24。

在高度数组 ht = [3, 8, 5, 2, 7, 7, 3, 4](索引 0 至 7)中,容器容量定义为 cap[i, j] = min(ht[i], ht[j]) × (j - i)。

与图 15-9 从初始状态 [0, 7] 向内移动长板的情况相对照,本图从同一起点右移左侧短板指针。起点两板高 3、4,容量为 21。

画面中右指针保持在 j = 7(高度 4),左指针从索引 0 向右移动一格至 i = 1(高度 ht[1] = 8,原索引 0 的隔板恢复为未选中灰柱)。此时左板高度 8 超过右板高度 4,新的短板转移到右端 j = 7;横跨索引 1 至 7、高度齐平右板 4 的浅蓝色矩形表示更新后的盛水区域,图下方标注“向内移动短板,容量可能增大”及当前容量算式。

移动后宽度从 7 缩为 6,水高从 3 升为 4;图中算式为 cap = min(8, 4) × (7 - 1) = 24。这说明向内移动短板有可能增大容量,并非每次都会增大。24 仍不是全数组最大值;图 15-7 给出的最优端点为 [1, 5],容量为 28。

由此便可推出本题的贪心策略:初始化两指针,使其分列容器两端,每轮向内收缩短板对应的指针,直至两指针相遇。

图 15-11 展示了贪心策略的执行过程。

  1. 初始状态下,指针 \(i\) 和 \(j\) 分列数组两端。
  2. 计算当前状态的容量 \(cap[i, j]\) ,并更新最大容量。
  3. 比较板 \(i\) 和板 \(j\) 的高度,并将短板向内移动一格。
  4. 循环执行第 2. 步和第 3. 步,直至 \(i\) 和 \(j\) 相遇时结束。

图 15-11   最大容量问题的贪心过程

图解 15-11:最大容量:双指针贪心

双指针从两端向内移动较短隔板,每次计算当前容量并保存历史最大值,最终返回 28。

给定高度数组 ht = [3, 8, 5, 2, 7, 7, 3, 4](索引 0 至 7),容器容量为 cap[i, j] = min(ht[i], ht[j]) × (j - i)。

双指针贪心算法初始化左指针 i = 0、右指针 j = 7、最大容量记录 res = 0。当 i < j 时循环执行:先计算当前容量 cap 并用 res = max(res, cap) 更新全局最大值,然后比较左右两板高度,将较短一侧的指针向内移动一格,直到 i 与 j 相遇时跳出循环。

图组共 9 步:选中隔板上方以青绿色标签 i 和蓝色标签 j 标出左右指针位置,选中隔板以对应颜色突出;第 2 至 8 步两板间的当前容器以浅蓝色区域填充,图下方给出当前轮的 cap 计算式与已知最大值 res 的更新式。

第 1 步仅初始化,第 2 至 8 步共进行 7 次容量计算,第 9 步相遇退出;播放器步号不等于容量计算次数。列表后的“最大容量第 2 至 8 步:计算与历史最大值”表按步号汇总数值;指针位置和 cap、res 在图中有标注,板高按坐标轴读出。

  1. 初始化两端指针

    初始化左指针 i = 0(指向左端高度 3 的隔板)、右指针 j = 7(指向右端高度 4 的隔板),并将容量最大值初始化为 res = 0。此时尚未开始第一轮盛水容量计算。图中尚未绘制盛水区域。

  2. 计算容器 [0, 7] 的容量

    首次计算,考察两端状态 [0, 7]:左板高 ht[0] = 3,右板高 ht[7] = 4,宽度为 7 - 0 = 7,当前容量 cap = min(3, 4) × 7 = 21;最大容量更新为 res = max(0, 21) = 21。由于左板 3 短于右板 4,下一步将左端短板指针 i 向右移动。

  3. 右移短板指针至 i = 1

    因上一轮左板更短,左指针 i 从 0 右移至 1,形成状态 [1, 7]:左板高 ht[1] = 8,右板高 ht[7] = 4,宽度为 7 - 1 = 6,当前容量 cap = min(8, 4) × 6 = 24;最大容量更新为 res = max(21, 24) = 24。此时右板 4 短于左板 8,下一步改为左移右指针 j。

  4. 左移短板至 j = 6

    因上一轮右板高 4 短于左板高 8,右指针 j 从 7 左移至 6,形成状态 [1, 6]:左板高 8,右板高 ht[6] = 3,宽度为 6 - 1 = 5,当前容量 cap = min(8, 3) × 5 = 15;与历史最大值比较,res = max(24, 15) = 24 保持不变。

  5. 左移短板至 j = 5

    因上一轮右板高 3 短于左板高 8,右指针 j 从 6 左移至 5,形成状态 [1, 5]:左板高 8,右板高 ht[5] = 7,宽度为 5 - 1 = 4,当前容量 cap = min(8, 7) × 4 = 28;历史最大值更新为 res = max(24, 28) = 28。

  6. 左移短板至 j = 4

    因上一轮右板高 7 短于左板高 8,右指针 j 从 5 左移至 4,形成状态 [1, 4]:左板高 8,右板高 ht[4] = 7,宽度为 4 - 1 = 3,当前容量 cap = min(8, 7) × 3 = 21;历史最大值 res = max(28, 21) = 28 保持不变。

  7. 左移短板至 j = 3

    因上一轮右板高 7 短于左板高 8,右指针 j 从 4 左移至 3,形成状态 [1, 3]:左板高 8,右板高 ht[3] = 2,宽度为 3 - 1 = 2,当前容量 cap = min(8, 2) × 2 = 4;历史最大值 res = max(28, 4) = 28 保持不变。

  8. 左移短板至 j = 2

    因上一轮右板高 2 短于左板高 8,右指针 j 从 3 左移至 2,形成状态 [1, 2]:左板高 8,右板高 ht[2] = 5,宽度为 2 - 1 = 1,当前容量 cap = min(8, 5) × 1 = 5;历史最大值 res = max(28, 5) = 28 保持不变。

  9. 两指针相遇,返回最大容量

    右板高 5 仍短于左板高 8,右指针 j 从 2 左移至 1,与 i 相遇。图中 i、j 双色标签合并在索引 1 的隔板上方;横轴数字 2 虽仍为蓝色,但不是当前指针位置。此时 i < j 不成立,不再计算新容量,退出循环并返回 res = 28。

最大容量第 2 至 8 步:计算与历史最大值
图解步骤ij左板高右板高当前容量 cap已知最大值 res
第 2 步07342121
第 3 步17842424
第 4 步16831524
第 5 步15872828
第 6 步14872128
第 7 步1382428
第 8 步1285528

2.   代码实现

代码循环最多 \(n\) 轮,因此时间复杂度为 \(O(n)\) 。

变量 \(i\)、\(j\)、\(res\) 使用常数大小的额外空间,因此空间复杂度为 \(O(1)\) 。

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   移动短板导致被跳过的状态

图解 15-12:移动短板导致被跳过的状态

双指针从 cap[0, 7] 向内移动左短板至 cap[1, 7] 时,一次性跳过了仍以索引 0 为左板、右端为 6 至 1 的六个更窄状态。

本例高度数组见下方“输入隔板高度”表,索引从 0 开始。初始端点 [0, 7] 的两板高 3、4,左板较短;容量为 min(3, 4) × 7 = 21。

容器容量 cap[i, j] = min(ht[i], ht[j]) × (j - i),水高取较小板高,宽度取索引差。

上排以向右箭头标出 cap[0, 7] → cap[1, 7],箭头上写“移动短板”。下方“跳过的状态”括线覆盖两行三列小图,均固定 i = 0,按行从左到右令 j 为 6、5、4、3、2、1。

下方两表分别给出示例输入和六个跳过状态。图面仅标 cap[i, j] 状态名;表中的具体板高、水高、宽度和容量由“输入隔板高度”表及公式推算。

输入隔板高度;索引从0开始
索引高度
03
18
25
32
47
57
63
74
六个跳过状态;容量由高度数组按公式计算
端点 [i,j]水高 min(ht[i],ht[j])宽度 j-i容量
[0,6]3618
[0,5]3515
[0,4]3412
[0,3]236
[0,2]326
[0,1]313

六个状态的宽度都小于 7,水高至多为原左板高度 3,因此容量都小于已记录的 21,跳过它们不会漏掉最优解。其中 [0, 3] 的右板高 2,比左板更矮,故水高降为 2、宽度为 3、容量为 6;其余五个状态水高为 3。

观察发现,这些被跳过的状态实际上就是将长板 \(j\) 向内移动的所有状态。前面我们已经证明内移长板一定会导致容量变小。也就是说,被跳过的状态都不可能是最优解,跳过它们不会导致错过最优解。

以上分析说明,移动短板的操作是“安全”的,贪心策略是有效的。

欢迎在评论区留下你的见解、问题或建议