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}$.

Python3

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        g = []
        for x in nums:
            l, r = 0, len(g)
            while l < r:
                mid = (l + r) >> 1
                if g[mid] < x:
                    r = mid
                else:
                    l = mid + 1
            if l == len(g):
                g.append(x)
            else:
                g[l] = x
        return len(g)

Java

class Solution {
    public int minOperations(int[] nums) {
        List<Integer> g = new ArrayList<>();
        for (int x : nums) {
            int l = 0, r = g.size();
            while (l < r) {
                int mid = (l + r) >> 1;
                if (g.get(mid) < x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l == g.size()) {
                g.add(x);
            } else {
                g.set(l, x);
            }
        }
        return g.size();
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        vector<int> g;
        for (int x : nums) {
            int l = 0, r = g.size();
            while (l < r) {
                int mid = (l + r) >> 1;
                if (g[mid] < x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l == g.size()) {
                g.push_back(x);
            } else {
                g[l] = x;
            }
        }
        return g.size();
    }
};

Go

func minOperations(nums []int) int {
	g := []int{}
	for _, x := range nums {
		l, r := 0, len(g)
		for l < r {
			mid := (l + r) >> 1
			if g[mid] < x {
				r = mid
			} else {
				l = mid + 1
			}
		}
		if l == len(g) {
			g = append(g, x)
		} else {
			g[l] = x
		}
	}
	return len(g)
}

TypeScript

function minOperations(nums: number[]): number {
    const g: number[] = [];
    for (const x of nums) {
        let [l, r] = [0, g.length];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (g[mid] < x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l === g.length) {
            g.push(x);
        } else {
            g[l] = x;
        }
    }
    return g.length;
}

Rust

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut g = Vec::new();
        for &x in nums.iter() {
            let mut l = 0;
            let mut r = g.len();
            while l < r {
                let mid = (l + r) / 2;
                if g[mid] < x {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if l == g.len() {
                g.push(x);
            } else {
                g[l] = x;
            }
        }
        g.len() as i32
    }
}