What is the Min Max Game problem?

The Min Max Game problem asks you to simulate a reduction process on an array where you apply pairwise minimum or maximum operations until one number remains.

How can I solve the Min Max Game problem efficiently?

To solve it efficiently, simulate the reduction process iteratively, reducing the array by half in each step while applying the minimum for even indices and the maximum for odd indices.

What is the time complexity of the Min Max Game problem?

The time complexity is O(n), where n is the length of the array, because the size of the array is halved with each reduction step.

Are there any edge cases to consider in the Min Max Game problem?

Yes, edge cases include when the array has only one element or when all elements in the array are equal.

What patterns does the Min Max Game problem focus on?

The problem focuses on array simulation and the efficient application of pairwise operations to reduce the array.

#2293

Easy

auto_awesome数组·模拟

LeetCode 题解工作台

极大极小游戏

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。对 nums 执行下述算法：设 n 等于 nums 的长度，如果 n == 1 ，终止算法过程。否则，创建一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。对于满足 0 的每个偶数下…

数组模拟

题目描述

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。

对 nums 执行下述算法：

设 n 等于 nums 的长度，如果 n == 1 ，终止算法过程。否则，创建一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。
对于满足 0 <= i < n / 2 的每个偶数下标 i ，将 newNums[i] 赋值为 min(nums[2 * i], nums[2 * i + 1]) 。
对于满足 0 <= i < n / 2 的每个奇数下标 i ，将 newNums[i] 赋值为 max(nums[2 * i], nums[2 * i + 1]) 。
用 newNums 替换 nums 。
从步骤 1 开始重复整个过程。

执行算法后，返回 nums 中剩下的那个数字。

示例 1：

输入：nums = [1,3,5,2,4,8,2,2]
输出：1
解释：重复执行算法会得到下述数组。
第一轮：nums = [1,5,4,2]
第二轮：nums = [1,4]
第三轮：nums = [1]
1 是最后剩下的那个数字，返回 1 。

示例 2：

输入：nums = [3]
输出：3
解释：3 就是最后剩下的数字，返回 3 。

提示：

1 <= nums.length <= 1024
1 <= nums[i] <= 10⁹
nums.length 是 2 的幂

lightbulb

解题思路

方法一：模拟

根据题意，我们可以模拟整个过程，最后剩下的数字即为答案。在实现上，我们不需要额外创建数组，直接在原数组上进行操作即可。

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

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        while n > 1:
            n >>= 1
            for i in range(n):
                a, b = nums[i << 1], nums[i << 1 | 1]
                nums[i] = min(a, b) if i % 2 == 0 else max(a, b)
        return nums[0]

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate correctly simulates the process without overcomplicating the solution.
question_mark
The candidate handles edge cases and large inputs efficiently.
question_mark
The candidate explains how the time complexity is reduced with each step of the iteration.

warning

常见陷阱

外企场景

error
Misunderstanding the problem and applying the wrong operation for even and odd indices.
error
Not recognizing that the length of the array is halved at each step, which can lead to inefficient solutions.
error
Failing to handle edge cases such as when the array has only one element or when all elements are equal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Simulate with different operations (min vs max), alternating by indices or positions.
arrow_right_alt
Modify the problem to find the minimum/maximum value of the remaining number, instead of just the last one.
arrow_right_alt
Apply the same process but with different array lengths (not restricted to power of 2).

help

常见问题

外企场景

继续练习

#2295 替换数组中的元素 #2303 计算应缴税款总额 #2326 螺旋矩阵 IV