删除数对后的最小数组长度

You are given a 0-indexed sorted array of integers nums.

You can perform the following operation any number of times:

• Choose two indices, i and j, where i < j, such that nums[i] < nums[j].
• Then, remove the elements at indices i and j from nums. The remaining elements retain their original order, and the array is re-indexed.

Return an integer that denotes the minimum length of nums after performing the operation any number of times (including zero).

Note that nums is sorted in non-decreasing order.

 

Example 1:

Input: nums = [1,3,4,9]
Output: 0
Explanation: Initially, nums = [1, 3, 4, 9].
In the first operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 1 < 3.
Remove indices 0 and 1, and nums becomes [4, 9].
For the next operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 4 < 9.
Remove indices 0 and 1, and nums becomes an empty array [].
Hence, the minimum length achievable is 0.

Example 2:

Input: nums = [2,3,6,9]
Output: 0
Explanation: Initially, nums = [2, 3, 6, 9]. 
In the first operation, we can choose index 0 and 2 because nums[0] < nums[2] <=> 2 < 6. 
Remove indices 0 and 2, and nums becomes [3, 9]. 
For the next operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 3 < 9. 
Remove indices 0 and 1, and nums becomes an empty array []. 
Hence, the minimum length achievable is 0.

Example 3:

Input: nums = [1,1,2]
Output: 1
Explanation: Initially, nums = [1, 1, 2].
In an operation, we can choose index 0 and 2 because nums[0] < nums[2] <=> 1 < 2. 
Remove indices 0 and 2, and nums becomes [1]. 
It is no longer possible to perform an operation on the array. 
Hence, the minimum achievable length is 1. 

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• nums is sorted in non-decreasing order.

/*
 * 思路：
 * 与Java版本相同，通过流操作简化代码。
 * 仍然是寻找最长的不下降子序列，然后剩余的元素就是我们需要移除的。
 */

import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public int minLengthAfterRemovals(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        IntStream.range(1, n).forEach(i -> 
            IntStream.range(0, i).forEach(j -> {
                if (nums[i] >= nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            })
        );
        int maxLength = Arrays.stream(dp).max().orElse(1);
        return n - maxLength;
    }
}

此题解的核心思路在于找出数组中的中间值，并确定这个值的最大出现次数。由于数组是非递减的，这个中间值可以代表数组的中值或众数。题解利用这个中间值的最大出现次数，尝试将数组分成尽可能多的配对，每对满足较小数小于较大数的条件，从而使数组长度最小化。由于每次操作都会移除两个数字，所以解集中考虑了两种情况：1) 若最大出现次数乘以二小于数组长度，返回数组长度取模二的结果；2) 若不小于，则返回0或1，具体取决于数组长度是奇数还是偶数。这种方法有效地利用了数组的非递减特性，通过统计中间值的出现频率来最大化配对的可能。

O(log n)

O(1)