LeetCode第240场周赛题解
方法1
- 思路：有序集合 + 计数
- 用有序哈希表直接把所有年份都存起来，找到第一个人口最多的年份返回即可
class Solution {
public int maximumPopulation(int[][] logs) {
int res = 0;
TreeMap<Integer,Integer> map = new TreeMap<>();
int maxv = 0;
for(int[] x: logs){
int a = x[0], b = x[1];
for(int i = a; i < b; i++){
map.put(i, map.getOrDefault(i, 0) + 1);
maxv = Math.max(maxv, map.get(i));
}
}
int last = 0;
for(int k: map.keySet()){
if(map.get(k) == maxv){
res = k;
return k;
}
}
return 0;
}
}
- 时间复杂度：$O(n \times k \times logn)$，k为年份最大最小的差值
- 空间复杂度：$O(n)$
方法2
class Solution {
public int maximumPopulation(int[][] logs) {
TreeMap<Integer,Integer> d = new TreeMap<>();
for(int[] log: logs){
d.put(log[0], d.getOrDefault(log[0], 0) + 1);
d.put(log[1], d.getOrDefault(log[1], 0) - 1);
}
int sum = 0;
int maxv = 0;
int res = 0;
for(Map.Entry<Integer,Integer> kv: d.entrySet()){
sum += kv.getValue();
if(sum > maxv){
maxv = sum;
res = kv.getKey();
}
}
return res;
}
}
- 时间复杂度：$O(nlogn)$
- 空间复杂度：$O(n)$
class Solution {
public int maximumPopulation(int[][] logs) {
int[] d = new int[110];
for(int[] log: logs){
d[log[0] - 1950]++;
d[log[1] - 1950]--;
}
int sum = 0;
int maxv = 0;
int res = 0;
for(int i = 0; i < 101; i++){
sum += d[i];
if(sum > maxv){
maxv = sum;
res = i;
}
}
return res + 1950;
}
}
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
- 思路：双指针
- 由于两个数组都有序，我们可以用两个指针倒序遍历两个数组：
- 如果
b[j] >= a[i]，如果下标也满足j - i >= 0，则记录答案，然后i--判断更大的a[i]能否满足条件
- 如果
b[j] < a[i]，说明b[j]不能满足条件，需要增大b[j]
class Solution {
public int maxDistance(int[] a, int[] b) {
int n = a.length, m = b.length;
int i = n-1, j = m-1;
int res = 0;
while(i >= 0 && j >= 0){
if(b[j] >= a[i]){
if(j >= i) res = Math.max(res, j - i);
i--;
}else{
j--;
}
}
return res;
}
}
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
- 思路：前缀和 + 单调栈
- 对于每个位置
i，我们可以找到左侧离i最远的j使得a[j] >= a[i]；右侧离i最远的k，使得a[k] >= a[i]，且j和k都可以和i相同
- 例如：对于
[1, 2, 3, 2]，l为[0, 1, 2, 1]，r为[3, 3, 2, 3]
- 预处理完两个数组后，
a[i]作为最小值的子数组所能获得的最小乘积为a[i] * (s[r[i]+1] - s[l[i]])
class Solution {
public int maxSumMinProduct(int[] nums) {
long res = 0;
int mod = (int)1e9 + 7;
int n = nums.length;
long[] s = new long[n+1];
for(int i = 1; i <= n; i++) s[i] = s[i-1] + nums[i-1];
Deque<Integer> stk = new ArrayDeque<>();
int[] l = new int[n];
int[] r = new int[n];
for(int i = 0; i < n; i++){
while(stk.size() > 0 && nums[stk.peek()] >= nums[i]) stk.pop();
l[i] = stk.size() == 0 ? 0 : stk.peek() + 1;
stk.push(i);
}
stk.clear();
for(int i = n - 1; i >= 0; i--){
while(stk.size() > 0 && nums[stk.peek()] >= nums[i]) stk.pop();
r[i] = stk.size() == 0 ? n-1 : stk.peek() - 1;
stk.push(i);
}
for(int i = 0; i < n; i++){
res = Math.max(res, (long)nums[i] * (s[r[i] + 1] - s[l[i]]));
}
return (int)(res % mod);
}
}
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
- 思路：拓扑排序 + 动态规划
- 前置知识：LeetCode210.课程表 II
- 先求出有向图的拓扑序列，如果有环直接返回
-1，然后在拓扑序列上做动态规划
- 状态定义：
f[i][j]表示以i为终点，且路径上j出现次数的最大值，答案为f[i][j]，其中i为[0, n-1]，j为[0, 25]
- 状态转移：对于
u指向v的有向边，有f[v][i] = max(f[v][i], f[u][i] + x)，其中i的取值是[0, 25]，且x在v与i颜色相同时为1，否则为0
class Solution {
public int largestPathValue(String colors, int[][] edges) {
int n = colors.length(), m = edges.length;
Map<Integer,List<Integer>> g = new HashMap<>();
int[] d = new int[n];
for(int[] edge: edges){
int a = edge[0], b = edge[1];
d[b]++;
g.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
}
Queue<Integer> q = new LinkedList<>();
int cnt = 0;
int[] topo = new int[n];
// f[i][j]: 路径终点为i, 颜色j出现次数的最大值
int[][] f = new int[n][26];
int res = 0;
for(int i = 0; i < n; i++){
if(d[i] == 0) {
q.offer(i);
}
}
while(q.size() > 0){
int t = q.poll();
topo[cnt++] = t;
if(g.containsKey(t)){
for(int x: g.get(t)){
if(--d[x] == 0){
q.offer(x);
}
}
}
}
if(cnt != n) return -1;
System.out.println(Arrays.toString(topo));
for(int u: topo){
int c = colors.charAt(u) - 'a';
f[u][c] = Math.max(f[u][c], 1);
for(int i = 0; i < 26; i++){
if(g.containsKey(u)){
for(int v: g.get(u)){
f[v][i] = Math.max(f[v][i], f[u][i] + (colors.charAt(v) - 'a' == i ? 1 : 0));
}
}
res = Math.max(res, f[u][i]);
}
}
return res;
}
}
- 时间复杂度：$O(n * c)$，n为节点数，c为字符集数
- 空间复杂度：$O(n * c)$
