代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定一个未排序的整数数组 nums
, 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。
提示:
1 <= nums.length <= 2000
-106 <= nums[i] <= 106
这是最长递增子序列的变形题。
方法一:动态规划
除了原有的 dp
数组之外,另加了 cnt
数组记录以 nums[i]
结尾的最长子序列的个数。
时间复杂度 $O(n^2)$。
方法二:树状数组
树状数组,也称作“二叉索引树”(Binary Indexed Tree)或 Fenwick 树。 它可以高效地实现如下两个操作:
update(x, delta)
: 把序列 x 位置的数加上一个值 delta;query(x)
:查询序列 [1,...x]
区间的区间和,即位置 x 的前缀和。这两个操作的时间复杂度均为 $O(\log n)$。当数的范围比较大时,需要进行离散化,即先进行去重并排序,然后对每个数字进行编号。
本题我们使用树状数组 tree[x]
来维护以 x 结尾的最长上升子序列的长度,以及该长度对应的子序列个数。
时间复杂度 $O(n\log n)$。
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
maxLen, ans, n = 0, 0, len(nums)
dp, cnt = [1] * n, [1] * n
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
elif dp[j] + 1 == dp[i]:
cnt[i] += cnt[j]
if dp[i] > maxLen:
maxLen = dp[i]
ans = cnt[i]
elif dp[i] == maxLen:
ans += cnt[i]
return ans
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
self.d = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, val, cnt):
while x <= self.n:
if self.c[x] < val:
self.c[x] = val
self.d[x] = cnt
elif self.c[x] == val:
self.d[x] += cnt
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
val = cnt = 0
while x:
if self.c[x] > val:
val = self.c[x]
cnt = self.d[x]
elif self.c[x] == val:
cnt += self.d[x]
x -= BinaryIndexedTree.lowbit(x)
return val, cnt
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
s = sorted(set(nums))
m = {v: i for i, v in enumerate(s, 1)}
n = len(m)
tree = BinaryIndexedTree(n)
ans = 0
for v in nums:
x = m[v]
val, cnt = tree.query(x - 1)
tree.update(x, val + 1, max(cnt, 1))
return tree.query(n)[1]
class Solution {
public int findNumberOfLIS(int[] nums) {
int maxLen = 0, ans = 0, n = nums.length;
int[] dp = new int[n];
int[] cnt = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
cnt[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
} else if (dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i];
} else if (dp[i] == maxLen) {
ans += cnt[i];
}
}
return ans;
}
}
class Solution {
public int findNumberOfLIS(int[] nums) {
TreeSet<Integer> ts = new TreeSet();
for (int v : nums) {
ts.add(v);
}
int idx = 1;
Map<Integer, Integer> m = new HashMap<>();
for (int v : ts) {
m.put(v, idx++);
}
int n = m.size();
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int v : nums) {
int x = m.get(v);
int[] t = tree.query(x - 1);
tree.update(x, t[0] + 1, Math.max(t[1], 1));
}
return tree.query(n)[1];
}
}
class BinaryIndexedTree {
private int n;
private int[] c;
private int[] d;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
d = new int[n + 1];
}
public void update(int x, int val, int cnt) {
while (x <= n) {
if (c[x] < val) {
c[x] = val;
d[x] = cnt;
} else if (c[x] == val) {
d[x] += cnt;
}
x += lowbit(x);
}
}
public int[] query(int x) {
int val = 0;
int cnt = 0;
while (x > 0) {
if (val < c[x]) {
val = c[x];
cnt = d[x];
} else if (val == c[x]) {
cnt += d[x];
}
x -= lowbit(x);
}
return new int[] {val, cnt};
}
public static int lowbit(int x) {
return x & -x;
}
}
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int maxLen = 0, ans = 0, n = nums.size();
vector<int> dp(n, 1), cnt(n, 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
} else if (dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i];
} else if (dp[i] == maxLen) {
ans += cnt[i];
}
}
return ans;
}
};
class BinaryIndexedTree {
public:
int n;
vector<int> c;
vector<int> d;
BinaryIndexedTree(int _n)
: n(_n)
, c(_n + 1)
, d(n + 1) {}
void update(int x, int val, int cnt) {
while (x <= n) {
if (c[x] < val) {
c[x] = val;
d[x] = cnt;
} else if (c[x] == val)
d[x] += cnt;
x += lowbit(x);
}
}
vector<int> query(int x) {
int val = 0, cnt = 0;
while (x > 0) {
if (val < c[x]) {
val = c[x];
cnt = d[x];
} else if (val == c[x])
cnt += d[x];
x -= lowbit(x);
}
return {val, cnt};
}
int lowbit(int x) {
return x & -x;
}
};
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
set<int> s(nums.begin(), nums.end());
int idx = 1;
unordered_map<int, int> m;
for (int v : s) m[v] = idx++;
int n = m.size();
BinaryIndexedTree* tree = new BinaryIndexedTree(n);
for (int v : nums) {
int x = m[v];
auto t = tree->query(x - 1);
tree->update(x, t[0] + 1, max(t[1], 1));
}
return tree->query(n)[1];
}
};
func findNumberOfLIS(nums []int) int {
maxLen, ans, n := 0, 0, len(nums)
dp, cnt := make([]int, n), make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
cnt[i] = 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
if dp[j]+1 > dp[i] {
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
} else if dp[j]+1 == dp[i] {
cnt[i] += cnt[j]
}
}
}
if dp[i] > maxLen {
maxLen = dp[i]
ans = cnt[i]
} else if dp[i] == maxLen {
ans += cnt[i]
}
}
return ans
}
type BinaryIndexedTree struct {
n int
c []int
d []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
d := make([]int, n+1)
return &BinaryIndexedTree{n, c, d}
}
func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}
func (this *BinaryIndexedTree) update(x, val, cnt int) {
for x <= this.n {
if this.c[x] < val {
this.c[x] = val
this.d[x] = cnt
} else if this.c[x] == val {
this.d[x] += cnt
}
x += this.lowbit(x)
}
}
func (this *BinaryIndexedTree) query(x int) []int {
var val, cnt int
for x > 0 {
if val < this.c[x] {
val = this.c[x]
cnt = this.d[x]
} else if val == this.c[x] {
cnt += this.d[x]
}
x -= this.lowbit(x)
}
return []int{val, cnt}
}
func findNumberOfLIS(nums []int) int {
s := make(map[int]bool)
for _, v := range nums {
s[v] = true
}
var t []int
for v, _ := range s {
t = append(t, v)
}
sort.Ints(t)
m := make(map[int]int)
for i, v := range t {
m[v] = i + 1
}
n := len(m)
tree := newBinaryIndexedTree(n)
for _, v := range nums {
x := m[v]
t := tree.query(x - 1)
tree.update(x, t[0]+1, max(t[1], 1))
}
return tree.query(n)[1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
impl Solution {
pub fn find_number_of_lis(nums: Vec<i32>) -> i32 {
let mut max_len = 0;
let mut ans = 0;
let n = nums.len();
let mut dp = vec![1; n];
let mut cnt = vec![1; n];
for i in 0..n {
for j in 0..i {
if nums[i] > nums[j] {
if dp[j] + 1 > dp[i] {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
} else if dp[j] + 1 == dp[i] {
cnt[i] += cnt[j];
}
}
}
if dp[i] > max_len {
max_len = dp[i];
ans = cnt[i];
} else if dp[i] == max_len {
ans += cnt[i];
}
}
ans
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。