3231. Minimum Number of Increasing Subsequence to Be Removed π
Description
Given an array of integers nums
, you are allowed to perform the following operation any number of times:
- Remove a strictly increasing subsequence from the array.
Your task is to find the minimum number of operations required to make the array empty.
Example 1:
Input: nums = [5,3,1,4,2]
Output: 3
Explanation:
We remove subsequences [1, 2]
, [3, 4]
, [5]
.
Example 2:
Input: nums = [1,2,3,4,5]
Output: 1
Example 3:
Input: nums = [5,4,3,2,1]
Output: 5
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
Solutions
Solution 1: Greedy + Binary Search
We traverse the array $\textit{nums}$ from left to right. For each element $x$, we need to greedily append it after the last element of the preceding sequence that is smaller than $x$. If no such element is found, it means the current element $x$ is smaller than all elements in the preceding sequences, and we need to start a new sequence with $x$.
From this analysis, we can observe that the last elements of the preceding sequences are in a monotonically decreasing order. Therefore, we can use binary search to find the position of the first element in the preceding sequences that is smaller than $x$, and then place $x$ in that position.
Finally, we return the number of sequences.
The time complexity is $O(n \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|