算法leetcode

leetcode第240场周赛：DAG的判定与DAG上的DP

字数统计: 3.7k字   |   阅读时长: 16分
,

摘要: 本文是 leetcode 第 240 周赛的记录。主要涉及的算法包括扫描线算法、双指针、单调栈、动态规划。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

这是 leetcode 第 240 场周赛，本场比赛的赞助公司是特赞，前 300 名可获得简历内推机会：

特赞是一家专注于内容与数字营销创新领域的公司，融合内容创意与计数创新，赋能商业。搭建创意内容的数字新基建，实现创意内容生产、管理、流转、分发的数据化、平台化、智能化，通过内容体验驱动品牌增长。基于特赞内容科技的积累，我们不断建立自研可控的数字创意技术底层能力，实践“Tech + Design”。

详细信息可以参考官网：

1
https://www.tezign.com/

本场比赛，依然是前 3 题完成比较好，但是 D 题没解决，最终成绩如下：

本场比赛考查的算法点包括扫描线算法、双指针、单调栈、DAG 上的 DP 等。亮点是 D 题结合了 DAG 的判定与 DAG 上的 DP。

各题的算法点以及参考文章如下：

A 题

给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。

返回 人口最多 且 最早 的年份。

示例 1：
输入：logs = [[1993,1999],[2000,2010]]
输出：1993
解释：人口最多为 1 ，而 1993 是人口为 1 的最早年份。
示例 2：
输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
输出：1960
解释：
人口最多为 2 ，分别出现在 1960 和 1970 。
其中最早年份是 1960 。

1
2
3
提示：
1 <= logs.length <= 100
1950 <= birthi < deathi <= 2050

算法: 扫描线算法

定义事件 Event，每个事件实例持有两个变量，一个年份 year，一个状态 kind，kind 为 1 表示出生，-1 表示死亡。

定义事件的排序规则，年份小的排在年份大的前面，当年份相同时，死亡排在出生前面。

遍历 logs 将其中的信息记录到事件数组 events 中，排序 events。然后遍历 events，过程中用 sum 维护当前活着的总人数，对每个事件 e，首先将 e.kind 累加到 sum，然后用 sum 与全局最大值对比，更新答案。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct Event
{
    int kind; // -1: 死亡, 1: 出生
    int year;
    Event(int kind, int y):kind(kind), year(y){}
    bool operator<(const Event& e) const
    {
        if(year == e.year)
            return kind < e.kind;
        return year < e.year;
    }
};

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<Event> events;
        for(const vector<int> &log: logs)
        {
            events.emplace_back(1, log[0]);
            events.emplace_back(-1, log[1]);
        }
        sort(events.begin(), events.end());
        int ans = 0;
        int max_sum = 0;
        int sum = 0;
        for(const Event &e: events)
        {
            sum += e.kind;
            if(sum > max_sum)
            {
                max_sum = sum;
                ans = e.year;
            }
        }
        return ans;
    }
};

B 题

给你两个 非递增 的整数数组 nums1 和 nums2，数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i​​ 。​​

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

示例 1：
输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。
示例 2：
输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。
示例 3：
输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。
示例 4：
输入：nums1 = [5,4], nums2 = [3,2]
输出：0
解释：不存在有效下标对，所以返回 0 。

1
2
3
4
5
提示：
1 <= nums1.length <= 1e5
1 <= nums2.length <= 1e5
1 <= nums1[i], nums2[j] <= 1e5
nums1 和 nums2 都是 非递增 数组

算法: 双串单向双指针

两个数组各维护一个从左向右推进的指针，nums1 的指针 i 和 nums2 的指针 j。首先 i 和 j 均初始化为 0，然后一轮一轮地持续推进，直到 i 或 j 推进到了数组末尾。

1
2
3
4
5
6
对于每一轮推进，刚开始的时候需要保证 i <= j:
    首先尽可能往前推进 j： 只要满足 `nums1[i] <= nums2[j]` 条件就向前推进 j，直到条件不满足或 j 到达末尾
    用 `(j - 1) - i` 更新答案
    如果 j 到达末尾则跳出循环
    调整 i，尽可能向前推进: 只要满足 `nums1[i] > nums2[j]` 条件就向前推进 i，直到条件不满足或 i 到达末尾
    调整 j: 因为 i 调整后可能会大于 j，将 j 调整为 `max(j, i)`，此时 j 可能到达或超出 nums2 的长度，这样自然不会进入下一轮推进

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        int i = 0, j = 0;
        int ans = 0;
        while(i < n1 && j < n2)
        {
            // 此时保证 i <= j
            // 尽可能往前推进 j
            while(j < n2 && nums1[i] <= nums2[j])
                ++j;
            ans = max(ans, (j - 1) - i);
            if(j == n2)
                break;
            // 向前调整 i
            while(i < n1 && nums1[i] > nums2[j])
                ++i;
            // 调整 i 后如果 i > j，需要调整 j
            j = max(j, i);
            // 此时 j 可能 >= n2
        }
        return ans;
    }
};

C 题

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 (3+2+5) = 2 10 = 20 。
给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 1e9 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

示例 1：
输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 (2+3+2) = 2 7 = 14 。
示例 2：
输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 (3+3) = 3 6 = 18 。
示例 3：
输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 (5+6+4) = 4 15 = 60 。

1
2
3
提示：
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e7

算法: 单调栈

对每个 nums 中的元素 nums[i]，求一次以 nums[i] 为最小值的【非空子数组 的最小乘积 的 最大值】，这些值中的最大值为所求答案。

对于 nums[i]，所求值 t 就是 nums[i] 乘以另一个值 y，这个 y 就是某个包含 i 的子区间 [j1, j2] 上的元素和，其中 nums 在 [j1, j2] 上的值都要大于等于 nums[i]。t = nums[i] * y ，要想使得所求值 t 最大，y 需要在满足条件的情况下取到最大。因为所有数都是正数，所以可以将 [j1, j2] 区间撑到最大。

问题变成了对每个 nums[i]，问其左侧第一个小于 nums[i] 的值在什么位置 s1, 其右侧第一个小于 nums[i] 的值在什么位置 s2，[s1 + 1, s2 - 1] 就是 [j1, j2]。

1
2
3
4
5
从左到右枚举 nums[i]，过程中维护一个栈，里面存放 [0..i-1] 的某些下标，这些下标在 nums 中的对应值是单调上升的:
首先将 x = nums[st.top()] 大于 nums[i] 的都弹出栈
栈顶的元素就是 x 左侧第一个小于 x 的值，nums[i] 就是 x 右侧第一个小于 x 的值
    这样就可以用 s1 = st.top(), s2 = i 来更新 x 对应的答案了
特殊值处理: 如果栈是空的，s1 为 0，如果 i 已经走到了 n，s2 为 n - 1

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        // 对每个 nums[i]，求以 nums[i] 为最小值的区间
        // 即求 [j1, j2]，对 j1 <= j<= j2 有 nums[i] <= nums[j]
        int n = nums.size();
        stack<int> st;
        using ll = long long;
        const int MOD = 1e9 + 7;
        ll ans = 0;
        vector<ll> sums(n + 1);
        for(int i = 0; i < n; ++i)
            sums[i + 1] = sums[i] + nums[i];
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && nums[st.top()] > nums[i])
            {
                ll min_x = nums[st.top()];
                st.pop();
                int right = i - 1;
                int left = 0;
                if(!st.empty())
                    left = st.top() + 1;
                ans = max(ans, min_x * (sums[right + 1] - sums[left]));
            }
            st.push(i);
        }
        while(!st.empty())
        {
            ll min_x = nums[st.top()];
            st.pop();
            int right = n - 1;
            int left = 0;
            if(!st.empty())
                left = st.top() + 1;
            ans = max(ans, min_x * (sums[right + 1] - sums[left]));
        }
        return ans % MOD;
    }
};

D 题

1857. 有向图中最大颜色值

给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。

给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条 有向边 。

图中一条有效 路径 是一个点序列 x1 -> x2 -> x3 -> … -> xk ，对于所有 1 <= i < k ，从 xi 到 xi+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。

请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。

示例 1：
输入：colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 “a” 的节点（上图中的红色节点）。
示例 2：
输入：colors = “a”, edges = [[0,0]]
输出：-1
解释：从 0 到 0 有一个环。

1
2
3
4
5
6
7
提示：
n == colors.length
m == edges.length
1 <= n <= 1e5
0 <= m <= 1e5
colors 只含有小写英文字母。
0 <= aj, bj < n

算法: DAG 判定, DAG上的DP

给定有向图 D，判定 D 是否为 DAG。有 DFS 和 BFS 两种方法。

(1) DFS 方法

维护一个全局的 visited 数组，定义如下。

1
2
3
visited[i] = 0 未考查过
visited[i] = 1 在当前搜索路径中
visited[i] = 2 已经考查过

枚举所有节点 u，如果 visited[u] 为 0，则以 u 为起点进行 DFS

DFS 过程中当前点为 u，如果在 for(int v: g[u]) 中发现 visited[v] == 1 则找到环。判定失败。

如果所有点都判定成功，则考察的图是 DAG

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DAGChecker_dfs
{
    bool dfs(const vector<vector<int> >& g, int node, vector<int>& visited)
    {
        if(visited[node] == 2)
            return true;
        if(visited[node] == 1) // 环
            return false;
        visited[node] = 1;
        for(int son: g[node])
            if(!dfs(g, son, visited))
                return false;
        visited[node] = 2;
        return true;
    }

public:
    bool operator()(const vector<vector<int>>& g) 
    {
        int n = g.size();
        vector<int> visited(n, 0);
        for(int i = 0; i < n; ++i)
        {
            if(visited[i] != 0) continue;
            if(!dfs(g, i, visited))
                return false;
        }
        return true;
    }
};

(2) BFS 方法

如果拓扑排序后的排序列表长度小于 n，则无法拓扑排序，即 D 不是 DAG。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class DAGChecker_bfs
{
public:
    bool operator()(const vector<vector<int>>& g, vector<int> indegrees)
    {
        int n = g.size();
        queue<int> q;
        for(int i = 0; i < n; ++i)
            if(indegrees[i] == 0)
                q.push(i);

        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            --n;
            for(int son: g[cur])
            {
                --indegrees[son];
                if(indegrees[son] == 0)
                    q.push(son);
            }
        }
        return n == 0;
    }
};
1
dp[u][s] := 以 u 开头，颜色 s 的最大颜色值是多少

以每个入度为 0 的点为起点 u 进行 dfs，dfs(u) 计算以 u 为起点，所有颜色可以取到的最大颜色值，保存在 dp[u][0~25] 中。dfs(u) 返回后，用 max(dp[u][0~25]) 更新答案。

在计算 dfs(u) 过程中，首先对 u 的所有子节点 v 递归地计算 dfs(v)，dfs(v) 返回后用所得的 dp[v][0~25] 信息更新 dp[u][0~25]。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class DAGChecker_dfs; // 模板
class DAGChecker_bfs; // 模板

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<vector<int>> g(n);
        vector<int> indegrees(n, 0);
        for(vector<int> &e: edges)
        {
            ++indegrees[e[1]];
            g[e[0]].push_back(e[1]);
        }
        DAGChecker_bfs dag_checker;
        // DAGChecker_dfs dag_checker;
        if(!dag_checker(g, indegrees))
            return -1;
        // g 是DAG
        int ans = 1;
        // dp[u][s] := 以 u 开头，颜色 s 的最大颜色值是多少
        dp = vector<vector<int>>(n, vector<int>(26, -1));
        for(int u = 0; u < n; ++u)
        {
            if(indegrees[u] > 0)
                continue;
            dfs(g, colors, u); // 以 i 为起点的最大颜色值
            for(int s = 0; s < 26; ++s)
            {
                ans = max(ans, dp[u][s]);
            }
        }
        return ans;
    }

private:
    vector<vector<int>> dp;

    void dfs(const vector<vector<int>>& g, const string& colors, int node)
    {
        if(dp[node][0] != -1)
            return;
        // node 开头的链还没算过
        for(int s = 0; s < 26; ++s)
            dp[node][s] = 0;
        for(int son: g[node])
        {
            dfs(g, colors, son);
            for(int s = 0; s < 26; ++s)
                dp[node][s] = max(dp[node][s], dp[son][s]);
        }
        ++dp[node][colors[node] - 'a'];
    }
};
Share