How do I approach the Maximum Score From Removing Stones problem?

You should apply a greedy approach where you always remove stones from the two largest piles to maximize the score.

Can I solve this problem without using a heap?

Yes, but using a heap allows you to manage the largest piles efficiently, making the solution optimal.

What is the time complexity of the solution?

The time complexity is O(log 3) for each heap operation, which is effectively constant for this problem.

How do I handle the edge case where one pile is much larger than the others?

Even in such cases, the greedy approach of always removing stones from the two largest piles remains optimal.

What is the most efficient way to implement this solution?

The most efficient implementation uses a priority queue (heap) to always access the two largest piles for each move.

#1753

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

移除石子的最大得分

你正在玩一个单人游戏，面前放置着大小分别为 a 、 b 和 c 的三堆石子。每回合你都要从两个不同的非空堆中取出一颗石子，并在得分上加 1 分。当存在两个或更多的空堆时，游戏停止。给你三个整数 a 、 b 和 c ，返回可以得到的最大分数。示例 1： …

数学贪心堆（优先队列）

题目描述

你正在玩一个单人游戏，面前放置着大小分别为 a、b 和 c 的三堆石子。

每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上加 1 分。当存在 两个或更多 的空堆时，游戏停止。

给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。

示例 1：

输入：a = 2, b = 4, c = 6
输出：6
解释：石子起始状态是 (2, 4, 6) ，最优的一组操作是：
- 从第一和第三堆取，石子状态现在是 (1, 4, 5)
- 从第一和第三堆取，石子状态现在是 (0, 4, 4)
- 从第二和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：6 分 。

示例 2：

输入：a = 4, b = 4, c = 6
输出：7
解释：石子起始状态是 (4, 4, 6) ，最优的一组操作是：
- 从第一和第二堆取，石子状态现在是 (3, 3, 6)
- 从第一和第三堆取，石子状态现在是 (2, 3, 5)
- 从第一和第三堆取，石子状态现在是 (1, 3, 4)
- 从第一和第三堆取，石子状态现在是 (0, 3, 3)
- 从第二和第三堆取，石子状态现在是 (0, 2, 2)
- 从第二和第三堆取，石子状态现在是 (0, 1, 1)
- 从第二和第三堆取，石子状态现在是 (0, 0, 0)
总分：7 分 。

示例 3：

输入：a = 1, b = 8, c = 8
输出：8
解释：最优的一组操作是连续从第二和第三堆取 8 回合，直到将它们取空。
注意，由于第二和第三堆已经空了，游戏结束，不能继续从第一堆中取石子。

提示：

1 <= a, b, c <= 10⁵

lightbulb

解题思路

方法一：贪心 + 模拟

每次贪心地从最大的两堆石子中取石头，直到至少有两堆石子为空。

时间复杂度 $O(n)$ ，其中 $n$ 为石子总数。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        s = sorted([a, b, c])
        ans = 0
        while s[1]:
            ans += 1
            s[1] -= 1
            s[2] -= 1
            s.sort()
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate effectively uses a greedy approach for optimal moves.
question_mark
They demonstrate understanding of heap operations to solve the problem efficiently.
question_mark
They correctly handle the edge case of one pile being much larger than the others.

warning

常见陷阱

外企场景

error
Not using a heap to efficiently track the largest piles.
error
Failing to account for the situation where fewer than two piles remain.
error
Overcomplicating the problem by not recognizing the greedy approach.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generalize to more than three piles of stones.
arrow_right_alt
Consider adding additional rules to the game, such as different scoring based on pile sizes.
arrow_right_alt
Modify the game to allow removing stones from any number of piles in each move.

help

常见问题

外企场景

继续练习

#1686 石子游戏 VI #1648 销售价值减少的颜色球 #1739 放置盒子