[Leetcode] 2293. Min Max Game

2293. Min Max Game

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.

For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).

For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).

Replace the array nums with newNums.

Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

Constraints:

1 <= nums.length <= 1024

1 <= nums[i] <= 10^9

nums.length is a power of 2.

Analysis

This question can be resolved by the classic Divide and Conquer algorithm.

The only extra thing is we need a flag to indicate whether it is the first half or the second half.

when flag == 0, we choose the min;

when flag == 1, we choose the max.

See the code below:

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        return f(nums, 0, nums.size(), 0);
    }
private:
    int f(vector<int>&ns, int left, int right, int flag) {
        if(left+1 == right) return ns[left];
        int mid = left + (right - left)/2;
        int x = f(ns, left, mid, 0), y = f(ns, mid, right, 1);
        return flag ? max(x, y) : min(x, y);
    }
};