How do I approach the 'Maximum Containers on a Ship' problem?

Start by calculating the number of containers the deck can hold, then check how many can be loaded without exceeding the maxWeight. Use simple math to find the solution.

What’s the time complexity of solving this problem?

The time complexity is O(1) with a direct calculation, but may vary based on optimization strategies or if complex algorithms are applied.

Can the number of containers exceed the ship's capacity?

No, the solution should ensure that the total weight does not exceed the ship's maxWeight by determining the number of containers that fit within the limit.

What strategy can I use to optimize this problem?

Focus on simple arithmetic to calculate the maximum number of containers that fit within the given weight constraint. Avoid unnecessary loops or iterations.

How does the grid dimension (n x n) affect the solution?

The grid dimension provides the maximum possible number of containers, but the actual number loaded is determined by the weight constraint maxWeight.

#3492

Easy

auto_awesome数学·driven

LeetCode 题解工作台

船上可以装载的最大集装箱数量

给你一个正整数 n ，表示船上的一个 n x n 的货物甲板。甲板上的每个单元格可以装载一个重量恰好为 w 的集装箱。然而，如果将所有集装箱装载到甲板上，其总重量不能超过船的最大承载重量 maxWeight 。请返回可以装载到船上的最大集装箱数量。示例 1：输入： n = 2, w …

数学

题目描述

给你一个正整数 n，表示船上的一个 n x n 的货物甲板。甲板上的每个单元格可以装载一个重量恰好为 w 的集装箱。

然而，如果将所有集装箱装载到甲板上，其总重量不能超过船的最大承载重量 maxWeight。

请返回可以装载到船上的最大集装箱数量。

示例 1：

输入： n = 2, w = 3, maxWeight = 15

输出： 4

解释：

甲板有 4 个单元格，每个集装箱的重量为 3。将所有集装箱装载后，总重量为 12，未超过 maxWeight。

示例 2：

输入： n = 3, w = 5, maxWeight = 20

输出： 4

解释：

甲板有 9 个单元格，每个集装箱的重量为 5。可以装载的最大集装箱数量为 4，此时总重量不超过 maxWeight。

提示：

1 <= n <= 1000
1 <= w <= 1000
1 <= maxWeight <= 10⁹

lightbulb

解题思路

方法一：数学

我们先计算出船上可以装载的最大重量，即 $n \times n \times w$ ，然后取其与 $\text{maxWeight}$ 的最小值，再除以 $w$ 即可。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
        return min(n * n * w, maxWeight) // w

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of how to calculate the number of containers under constraints
question_mark
Ability to apply greedy or straightforward math-based approaches
question_mark
Familiarity with optimizing math-driven solutions for large inputs

warning

常见陷阱

外企场景

error
Misunderstanding the weight limit and exceeding maxWeight
error
Not accounting for grid dimensions when calculating maximum capacity
error
Overcomplicating the solution with unnecessary steps like loops or conditionals

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the number of containers was restricted by a different factor, like deck shape or location?
arrow_right_alt
How would the solution change if container weights varied?
arrow_right_alt
What would the time complexity look like if n were in the order of magnitude of 1000?

help

常见问题

外企场景

继续练习

#3495 使数组元素都变为零的最少操作次数 #3505 使 K 个子数组内元素相等的最少操作数 #3512 使数组和能被 K 整除的最少操作次数