Skip to content

Latest commit

 

History

History
243 lines (196 loc) · 5.86 KB

README.md

File metadata and controls

243 lines (196 loc) · 5.86 KB
Raw
comments difficulty edit_url tags
true
困难
数组
二分查找

3231. 要删除的递增子序列的最小数量 🔒

English Version

题目描述

给定一个整数数组 nums，你可以执行任意次下面的操作：

  • 从数组删除一个 严格递增 的 子序列。

您的任务是找到使数组为 空 所需的 最小 操作数。

 

示例 1：

输入：nums = [5,3,1,4,2]

输出：3

解释：

我们删除子序列 [1, 2]，[3, 4]，[5]。

示例 2：

输入：nums = [1,2,3,4,5]

输出：1

示例 3：

输入：nums = [5,4,3,2,1]

输出：5

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

解法

方法一：贪心 + 二分查找

我们从左到右遍历数组 $\textit{nums}$，对于每个元素 $x$，我们需要贪心地将其追加到前面序列中最后一个元素小于 $x$ 的最大值后面。如果找不到这样的元素，则说明当前元素 $x$ 比前面序列中的所有元素都小，我们需要新开辟一个序列，将 $x$ 放入其中。

这样分析下来，我们可以发现，前面序列中的最后一个元素呈单调递减的状态。因此，我们可以使用二分查找来找到前面序列中最后一个元素小于 $x$ 的第一个元素位置，然后将 $x$ 放入该位置。

最终，我们返回序列的个数即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\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
    }
}