# # Leetcode 第240场周赛题解

## # Problem A - 人口最多的年份 (opens new window)

### # 方法一：暴力

• 时间复杂度$\mathcal{O}(ND)$
• 空间复杂度$\mathcal{O}(D)$

class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
cnt = [0] * 2051
for b, d in logs:
for j in range(b, d):
cnt[j] += 1
hi = 1950
for i in range(1950, 2050):
if cnt[i] > cnt[hi]:
hi = i
return hi

1
2
3
4
5
6
7
8
9
10
11

### # 方法二：差分数组

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度为$\mathcal{O}(D)$

class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
vector<int> cnt(101);
for (auto &log : logs)
cnt[log[0] - 1950]++, cnt[log[1] - 1950]--;
int hi = 0;
for (int i = 1; i < 101; ++i) {
cnt[i] += cnt[i - 1];
if (cnt[i] > cnt[hi])
hi = i;
}
return hi + 1950;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem B - 下标对中的最大距离 (opens new window)

### # 方法一：双指针

• 时间复杂度$\mathcal{O}(N+M)$
• 不考虑两个输入数组，空间复杂度$\mathcal{O}(1)$

class Solution {
public:
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
int ans = 0;
int ptr = -1;
for (int i = 0; i < n; ++i) {
while (ptr + 1 < m && nums1[i] <= nums2[ptr + 1])
ptr++;
ans = max(ans, ptr - i);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

## # Problem C - 子数组最小乘积的最大值 (opens new window)

### # 方法一：前缀和+单调栈

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

using ll = long long;
const ll MOD = 1e9 + 7;

class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
vector<ll> s(n + 1);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + nums[i - 1];

vector<int> l(n, 0), r(n, n - 1);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && nums[st.top()] > nums[i]) {
r[st.top()] = i - 1;
st.pop();
}
st.push(i);
}
st = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && nums[st.top()] > nums[i]) {
l[st.top()] = i + 1;
st.pop();
}
st.push(i);
}

ll ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, (s[r[i] + 1] - s[l[i]]) * nums[i]);

return ans % MOD;
}
};

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

## # Problem D - 有向图中最大颜色值 (opens new window)

### # 方法一：拓扑排序+DAG上动态规划

• 时间复杂度$\mathcal{O}((N+M)|\sum|)$
• 空间复杂度$\mathcal{O}(N+M)$

class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.size();
vector<int> deg(n);
for (auto &edge : edges) {
int u = edge[0], v = edge[1];
deg[v]++;
}

queue<int> q;
for (int i = 0; i < n; ++i) {
if (deg[i] == 0)
q.push(i);
}

vector<int> topo;
while (!q.empty()) {
int u = q.front();
q.pop();
topo.emplace_back(u);
for (int v : adj[u]) {
deg[v]--;
if (deg[v] == 0)
q.push(v);
}
}

if (topo.size() != n)
return -1;

int ans = 0;
for (int color = 0; color < 26; ++color) {
vector<int> dp(n);
for (int i = n - 1; i >= 0; --i) {
int u = topo[i];
for (int v : adj[u])
dp[u] = max(dp[u], dp[v]);
if (colors[u] - 'a' == color)
dp[u]++;
ans = max(ans, dp[u]);
}
}

return ans;
}
};

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