前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【综合笔试题】难度 3/5,多解法 LIS 问题

【综合笔试题】难度 3/5,多解法 LIS 问题

作者头像
宫水三叶的刷题日记
发布2021-06-23 10:52:49
6340
发布2021-06-23 10:52:49
举报

题目描述

这是 LeetCode 上的 「354. 俄罗斯套娃信封问题」 ,难度为 「困难」

给你一个二维整数数组 envelopes ,其中 envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

请计算「最多能有多少个」信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

注意:不允许旋转信封。

示例 1:

代码语言:javascript
复制
输入:envelopes = [[5,4],[6,4],[6,7],[2,3]]

输出:3

解释:最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2:

代码语言:javascript
复制
输入:envelopes = [[1,1],[1,1],[1,1]]

输出:1

提示:

  • 1 <= envelopes.length <= 5000
  • envelopes[i].length == 2
  • 1 <= wi, hi <=
10^4

动态规划

这是一道经典的 DP 模型题目:最长上升子序列(LIS)。

首先我们先对 envelopes 进行排序,确保信封是从小到大进行排序。

问题就转化为我们从这个序列中选择 k 个信封形成新的序列,使得新序列中的每个信封都能严格覆盖前面的信封(宽高都严格大于)。

我们可以定义状态

f[i]

为考虑前 i 个物品,并以第

i

个物品为结尾的最大值。

对于每个

f[i]

而言,最小值为

1

,代表只选择自己一个信封。

那么对于一般的

f[i]

该如何求解呢?因为第 i 件物品是必须选择的。我们可以枚举前面的

i - 1

件物品,哪一件可以作为第

i

件物品的上一件物品。

在前

i - 1

件物品中只要有符合条件的,我们就使用

\max(f[i], f[j] + 1)

更新

f[i]

然后在所有方案中取一个 max 即是答案。

代码:

代码语言:javascript
复制
class Solution {
    public int maxEnvelopes(int[][] es) {
        int n = es.length;
        if (n == 0) return n;
        // 因为我们在找第 i 件物品的前一件物品时,会对前面的 i - 1 件物品都遍历一遍,因此第二维(高度)排序与否都不影响
        Arrays.sort(es, (a, b)->a[0]-b[0]);
        int[] f = new int[n]; // f(i) 为考虑前 i 个物品,并以第 i 个物品为结尾的最大值
        int ans = 1;
        for (int i = 0; i < n; i++) {
            // 对于每个 f[i] 都满足最小值为 1
            f[i] = 1; 
            // 枚举第 i 件物品的前一件物品,
            for (int j = i - 1; j >= 0; j--) {
                // 只要有满足条件的前一件物品,我们就尝试使用 f[j] + 1 更新 f[i]
                if (check(es, j, i)) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            // 在所有的 f[i] 中取 max 作为 ans
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
    boolean check(int[][] es, int mid, int i) {
        return es[mid][0] < es[i][0] && es[mid][1] < es[i][1];
    }
}
  • 时间复杂度:
O(n^2)
  • 空间复杂度:
O(n)

二分 + 动态规划

上述方案其实算是一个朴素方案,复杂度是

O(n^2)

的,也是我最先想到思路,但是题目没有给出数据范围,也不知道能不能过。

唯唯诺诺交了一个居然过了。

下面讲下其他优化解法。

首先还是和之前一样,我们可以通过复杂度分析来想优化方向。

指数算法往下优化就是对数解法或者线性解法。

仔细观察朴素解法,其实可优化的地方主要就是找第

i

件物品的前一件物品的过程。

如果想要加快这个查找过程,我们需要使用某种数据结构进行记录。

并且是边迭代边更新数据结构里面的内容。

首先因为我们对 w 进行了排序(从小到大),然后迭代也是从前往后进行,因此我们只需要保证迭代过程中,对于 w 相同的数据不更新,就能保证 g 中只会出现满足 w 条件的信封。

到这一步,还需要用到的东西有两个:一个是 h,因为只有 wh 都同时满足,我们才能加入上升序列中;一个是信封所对应的上升序列长度,这是我们加速查找的核心。

我们使用数组 g 来记录,

g[i]

表示长度为

i

的最长上升子序列的中的最小「信封高度」,同时需要使用 len 记录当前记录到的最大长度。

还是不理解?没关系,我们可以直接看看代码,我把基本逻辑写在了注释当中(你的重点应该落在对

g[]

数组的理解上)。

代码:

代码语言:javascript
复制
class Solution {
    public int maxEnvelopes(int[][] es) {
        int n = es.length;
        if (n == 0) return n;
        // 由于我们使用了 g 记录高度,因此这里只需将 w 从小到达排序即可
        Arrays.sort(es, (a, b)->a[0] - b[0]);
        // f(i) 为考虑前 i 个物品,并以第 i 个物品为结尾的最大值
        int[] f = new int[n]; 
        // g(i) 记录的是长度为 i 的最长上升子序列的最小「信封高度」
        int[] g = new int[n]; 
        // 因为要取 min,用一个足够大(不可能)的高度初始化
        Arrays.fill(g, Integer.MAX_VALUE); 
        g[0] = 0;
        int ans = 1;
        for (int i = 0, j = 0, len = 1; i < n; i++) {
            // 对于 w 相同的数据,不更新 g 数组
            if (es[i][0] != es[j][0]) {
                // 限制 j 不能越过 i,确保 g 数组中只会出现第 i 个信封前的「历史信封」
                while (j < i) {
                    int prev = f[j], cur = es[j][1];
                    if (prev == len) {
                        // 与当前长度一致了,说明上升序列多增加一位
                        g[len++] = cur;
                    } else {
                        // 始终保留最小的「信封高度」,这样可以确保有更多的信封可以与其行程上升序列
                        // 举例:同样是上升长度为 5 的序列,保留最小高度为 5 记录(而不是保留任意的,比如 10),这样之后高度为 7 8 9 的信封都能形成序列;
                        g[prev] = Math.min(g[prev], cur);
                    }
                    j++;
                }
            }

            // 二分过程
            // g[i] 代表的是上升子序列长度为 i 的「最小信封高度」
            int l = 0, r = len;
            while (l < r) {
                int mid = l + r >> 1;
                // 令 check 条件为 es[i][1] <= g[mid](代表 w 和 h 都严格小于当前信封)
                // 这样我们找到的就是满足条件,最靠近数组中心点的数据(也就是满足 check 条件的最大下标)
                // 对应回 g[] 数组的含义,其实就是找到 w 和 h 都满足条件的最大上升长度
                if (es[i][1] <= g[mid]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            // 更新 f[i] 与答案
            f[i] = r;
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}
  • 时间复杂度:对于每件物品都是通过「二分」找到其前一件物品。复杂度为
O(n\log{n})
  • 空间复杂度:
O(n)

证明

我们可以这样做的前提是 g 数组具有二段性,可以通过证明其具有「单调性」来实现。

当然这里指的是 g 被使用的部分,也就是

[0, len - 1]

的部分。

我们再回顾一下 g[] 数组的定义:

g[i]

表示长度为

i

的最长上升子序列的中的最小「信封高度」

例如

g[] = [0, 3, 4, 5]

代表的含义是:

  • 上升序列长度为 0 的最小历史信封高度为 0
  • 上升序列长度为 1 的最小历史信封高度为 3
  • 上升序列长度为 2 的最小历史信封高度为 4
  • 上升序列长度为 3 的最小历史信封高度为 5

可以通过反证法来证明其单调性:

假设

g[]

不具有单调性,即至少有

g[i] > g[j]

(

i < j

,令

a = g[i]

,

b = g[j]

)

显然与我们的处理逻辑冲突。因为如果考虑一个「最小高度」为 b 的信封能够凑出长度为 j 的上升序列,自然也能凑出比 j 短的上升序列,对吧?

举个?,我们有信封:[[1,1],[2,2],[3,3],[4,4],[5,5]],我们能凑出很多种长度为 2 的上升序列方案,其中最小的方案是高度最小的方案是 [[1,1],[2,2]]。因此这时候 g[2] = 2,代表能凑出长度为 2 的上升序列所 「必须使用的信封」 的最小高度为 2。

这时候反过来考虑,如果使用 [2,2] 能够凑出长度为 2 的上升序列,必然也能凑出长度为 1 的上升序列(删除前面的其他信封即可)。

推而广之,如果我们有

g[j] = b

,也就是凑成长度为 j 必须使用的最小信封高度为 b。那么我必然能够保留高度为 b 的信封,删掉上升序列中的一些信封,凑成任意长度比 j 小的上升序列。

综上,

g[i] > g[j](i < j)

与处理逻辑冲突,

g[]

数组为严格单调上升数组。

既然

g[]

具有单调性,我们可以通过「二分」找到恰满足 check 条件的最大下标(最大下标达标表示最长上升序列长度)。

树状数组 + 动态规划

在「二分 + 动态规划」的解法中,我们通过「二分」来优化找第

i

个文件的前一个文件过程。

这个过程同样能通过「树状数组」来实现。

首先仍然是对 w 进行排序,然后使用「树状数组」来维护 h 维度的前缀最大值。

对于 h 的高度,我们只关心多个信封之间的大小关系,而不关心具体相差多少,我们需要对 h 进行离散化。

通常使用「树状数组」都需要进行离散化,尤其是这里我们本身就要使用

O(n)

的空间来存储 dp 值。

代码:

代码语言:javascript
复制
class Solution {
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }

    public int maxEnvelopes(int[][] es) {
        int n = es.length;
        if (n == 0) return n;

        // 由于我们使用了 g 记录高度,因此这里只需将 w 从小到达排序即可
        Arrays.sort(es, (a, b)->a[0] - b[0]);

        // 先将所有的 h 进行离散化
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) set.add(es[i][1]);
        int cnt = set.size();
        int[] hs = new int[cnt];
        int idx = 0;
        for (int i : set) hs[idx++] = i;
        Arrays.sort(hs);
        for (int i = 0; i < n; i++) es[i][1] = Arrays.binarySearch(hs, es[i][1]) + 1;

        // 创建树状数组
        tree = new int[cnt + 1];

        // f(i) 为考虑前 i 个物品,并以第 i 个物品为结尾的最大值
        int[] f = new int[n]; 
        int ans = 1;
        for (int i = 0, j = 0; i < n; i++) {
            // 对于 w 相同的数据,不更新 tree 数组
            if (es[i][0] != es[j][0]) {
                // 限制 j 不能越过 i,确保 tree 数组中只会出现第 i 个信封前的「历史信封」
                while (j < i) {
                    for (int u = es[j][1]; u <= cnt; u += lowbit(u)) {
                        tree[u] = Math.max(tree[u], f[j]);
                    }
                    j++;
                }
            }
            f[i] = 1;
            for (int u = es[i][1] - 1; u > 0; u -= lowbit(u)) {
                f[i] = Math.max(f[i], tree[u] + 1);
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}
  • 时间复杂度:处理每个物品时更新「树状数组」复杂度为
O(\log{n})

。整体复杂度为

O(n\log{n})
  • 空间复杂度:
O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.354 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-06-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 动态规划
  • 二分 + 动态规划
  • 证明
  • 树状数组 + 动态规划
  • 最后
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档