3828. 子数组删除后的最终元素

Medium

题目描述

给你一个整数数组 nums。

两个玩家 Alice 和 Bob 轮流玩游戏，Alice 先手。

• 在每一轮中，当前玩家选择任意子数组 nums[l..r]，使得 r - l + 1 < m，其中 m 是数组的当前长度。
• 选中的子数组被删除，剩余元素连接形成新数组。
• 游戏继续进行，直到只剩下一个元素。

Alice 的目标是最大化最终元素，而 Bob 的目标是最小化最终元素。假设两人都以最优策略进行游戏，返回最终剩余元素的值。

示例 1：

输入：nums = [1,5,2]
输出：2
解释：
一个有效的最优策略：
- Alice 删除 [1]，数组变为 [5, 2]。
- Bob 删除 [5]，数组变为 [2]。
因此，答案是 2。

示例 2：

输入：nums = [3,7]
输出：7
解释：
Alice 删除 [3]，数组变为 [7]。由于 Bob 此时无法进行操作，答案是 7。

约束条件：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

提示：

• 观察 Alice 第一步可以强制保护哪些位置，使得 Bob 之后无法删除它们。
• 任何中间元素都可以被 Bob 删除，所以只有端点可以被保护。
• Alice 选择更好的端点：答案是 max(nums[0], nums[nums.length - 1])。

解题思路

这道题目看似复杂，但通过分析游戏策略可以发现一个巧妙的规律。

核心观察：

1. 在每一步操作中，玩家只能删除长度小于当前数组长度的子数组，这意味着不能删除整个数组
2. Alice 想要最大化最终元素，Bob 想要最小化最终元素
3. 关键洞察：Alice 可以通过第一步操作来保护数组的某个端点元素

策略分析：

• 如果 Alice 在第一步删除除了 nums[0] 之外的所有元素（即删除 nums[1..n-1]），那么 nums[0] 就会成为最终元素
• 如果 Alice 在第一步删除除了 nums[n-1] 之外的所有元素（即删除 nums[0..n-2]），那么 nums[n-1] 就会成为最终元素
• 对于数组中间的任何元素，Bob 总是可以在后续回合中删除包含该元素的子数组来阻止它成为最终元素

最优策略： Alice 会选择保护 nums[0] 和 nums[n-1] 中较大的那个，因为她的目标是最大化最终元素。无论数组有多长，Alice 总是可以在第一步就决定最终结果。

因此，答案就是 max(nums[0], nums[nums.length - 1])。

代码实现

class Solution {
public:
    int finalElement(vector<int>& nums) {
        return max(nums[0], nums[nums.size() - 1]);
    }
};

class Solution:
    def finalElement(self, nums: List[int]) -> int:
        return max(nums[0], nums[-1])

public class Solution {
    public int FinalElement(int[] nums) {
        return Math.Max(nums[0], nums[nums.Length - 1]);
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var finalElement = function(nums) {
    return Math.max(nums[0], nums[nums.length - 1]);
};

复杂度分析