What is the main strategy for Eat Pizzas! problem?

The main strategy is to sort pizzas and use a greedy selection pairing the largest pizza with the three smallest remaining to maximize daily gain.

Why do we pick the second-largest pizza each day?

Because the problem defines that your weight gain from a group of four pizzas is the second-largest pizza's weight, enforcing the invariant rule.

Can this approach handle large n efficiently?

Yes, sorting takes O(n log n) and each day's selection is constant time, so the overall time complexity is O(n log n), suitable for large n.

What mistakes should I avoid with this greedy pattern?

Avoid not sorting, misidentifying the second-largest pizza, or failing to remove used pizzas from the array.

Are there variations of Eat Pizzas! using this greedy plus invariant pattern?

Yes, you can vary the group size or the rule for which pizza contributes to gain, but the greedy invariant approach still applies.

#3457

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

吃披萨

给你一个长度为 n 的整数数组 pizzas ，其中 pizzas[i] 表示第 i 个披萨的重量。每天你会吃恰好 4 个披萨。由于你的新陈代谢能力惊人，当你吃重量为 W 、 X 、 Y 和 Z 的披萨（其中 W ）时，你只会增加 1 个披萨的重量！体重增加规则如下：在奇数天（按 1 开始计…

数组贪心排序

题目描述

给你一个长度为 n 的整数数组 pizzas，其中 pizzas[i] 表示第 i 个披萨的重量。每天你会吃恰好 4 个披萨。由于你的新陈代谢能力惊人，当你吃重量为 W、X、Y 和 Z 的披萨（其中 W <= X <= Y <= Z）时，你只会增加 1 个披萨的重量！体重增加规则如下：

在 奇数天（按 1 开始计数）你会增加 Z 的重量。
在 偶数天，你会增加 Y 的重量。

请你设计吃掉所有披萨的最优方案，并计算你可以增加的最大总重量。

注意：保证 n 是 4 的倍数，并且每个披萨只吃一次。

示例 1：

输入： pizzas = [1,2,3,4,5,6,7,8]

输出： 14

解释：

第 1 天，你吃掉下标为 [1, 2, 4, 7] = [2, 3, 5, 8] 的披萨。你增加的重量为 8。
第 2 天，你吃掉下标为 [0, 3, 5, 6] = [1, 4, 6, 7] 的披萨。你增加的重量为 6。

吃掉所有披萨后，你增加的总重量为 8 + 6 = 14。

示例 2：

输入： pizzas = [2,1,1,1,1,1,1,1]

输出： 3

解释：

第 1 天，你吃掉下标为 [4, 5, 6, 0] = [1, 1, 1, 2] 的披萨。你增加的重量为 2。
第 2 天，你吃掉下标为 [1, 2, 3, 7] = [1, 1, 1, 1] 的披萨。你增加的重量为 1。

吃掉所有披萨后，你增加的总重量为 2 + 1 = 3。

提示：

4 <= n == pizzas.length <= 2 * 10⁵
1 <= pizzas[i] <= 10⁵
n 是 4 的倍数。

lightbulb

解题思路

方法一：贪心 + 排序

根据题目描述，我们每天可以吃 $4$ 个披萨。在奇数天，我们可以得到这 $4$ 个披萨中的最大值，而在偶数天，我们可以得到这 $4$ 个披萨中的第二大值。

因此，我们可以将披萨按重量从小到大排序，一共能吃 $\textit{days} = n / 4$ 天，那么一共有 $\textit{odd} = (\textit{days} + 1) / 2$ 天是奇数天，一共有 $\textit{even} = \textit{days} - \textit{odd}$ 天是偶数天。

考虑奇数天，我们可以选择最大的 $\textit{odd}$ 个披萨，以及最小的 $\textit{odd} \times 3$ 个披萨，增加的重量为 $\sum_{i = n - \textit{odd}}^{n - 1} \textit{pizzas}[i]$ 。

考虑偶数天，我们在剩余的披萨中，每次贪心地选择最大的两个披萨，以及最小的两个披萨，增加的重量为 $\sum_{i = n - \textit{odd} - 2}^{n - \textit{odd} - 2 \times \textit{even}} \textit{pizzas}[i]$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $\textit{pizzas}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxWeight(self, pizzas: List[int]) -> int:
        days = len(pizzas) // 4
        pizzas.sort()
        odd = (days + 1) // 2
        even = days - odd
        ans = sum(pizzas[-odd:])
        i = len(pizzas) - odd - 2
        for _ in range(even):
            ans += pizzas[i]
            i -= 2
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidate starts by sorting pizzas and reasoning about daily selections.
question_mark
Candidate identifies the invariant that gain is the second-largest pizza per day.
question_mark
Candidate efficiently removes selected pizzas and calculates running total gain.

warning

常见陷阱

外企场景

error
Forgetting to sort the array, leading to suboptimal pairing and total gain.
error
Incorrectly selecting the pizza to add to the gain (must be the second-largest in each group).
error
Not updating or removing pizzas properly after each day's selection, causing array misalignment.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the group size from four to another number with a similar invariant rule.
arrow_right_alt
Maximize total weight when gain is defined as the sum of the two largest pizzas per day.
arrow_right_alt
Introduce multiple days with alternating rules for which pizza contributes to gain.

help

常见问题

外企场景

继续练习

#3462 提取至多 K 个元素的最大总和 #3424 将数组变相同的最小代价 #3413 收集连续 K 个袋子可以获得的最多硬币数量