LeetCode Weekly Contest 240解题报告

No.1 人口最多的年份

解题思路

3 C/ a6 G/ c7 @+ s9 h数据范围比较小，直接枚举统计即可。

代码展示

1. 
   
2. class Solution {
   
3.     public int maximumPopulation(int[][] logs) {
   : r8 B9 u/ m, Q1 z# }
4.         int[] population = new int[2051];
   # A/ {! A1 p' C) j' ~$ V
5.         for (var log : logs) {
   
6.             for (int i = log[0]; i < log[1]; i++) {
   
7.                 population++;
   # k4 C( Y& y/ [: C9 Z1 d5 l7 ?: t, l
8.             }
   ! k. ~6 ~9 u1 J8 F2 D% ^
9.         }
     R$ P: o! W2 _3 E8 Y3 Y3 y
10.         int res = 1950;
    
11.         for (int i = 1951; i <= 2050; i++) {
    
12.             if (population > population[res]) {
    0 y& }, E8 x. M# f( G+ l  Y; l( A
13.                 res = i;
    % o5 t  g$ C2 I( A& s5 _/ C9 H7 E2 E
14.             }
    0 P: `' l$ p  g! F$ D; G
15.         }
    
16.         return res;
    - K+ J( V. a* @# w6 [+ n
17.     }
    
18. }

复制代码

. i/ C; H, d9 D- k8 f
No.2下标对中的最大距离
2 A0 V( L" Q  p8 j+ V
( `1 l% x/ T1 s& |解题思路
8 y0 W& r' \* M! I4 B
# c% R7 w; y% \2 o9 {6 w输入的两个数组都是单调的，可以使用双指针。

代码展示

1. class Solution {
   
2.     public int maxDistance(int[] nums1, int[] nums2) {
   
3.         int n = nums1.length, m = nums2.length;
     G9 L, A7 n$ g' F5 B# G; T
4.         int res = 0;
   4 `$ w4 }+ w) E( ^6 Y9 B9 R* A
5.         for (int i = 0, j = -1; i < n; i++) {
   9 G  d! s' ?. O3 U
6.             while (j + 1 < m && nums1 <= nums2[j + 1]) {
   , e+ i: V: F, Z4 l
7.                 j++;
   % W( P6 Z$ y% o4 ]7 R/ @9 i7 S
8.             }
   , F8 l8 c& n; i; y% ]
9.             res = Math.max(res, j - i);
   
10.         }
    , [, q  H) d2 I8 a- a
11.         return res;
    
12.     }
    3 i, P# j9 V; r/ g( W/ V, @" n  p6 b
13. }

复制代码

No.3 子数组最小乘积的最大值
; j* u" Y" Q6 z: i: f
解题思路
5 t; [/ G7 N' o8 }# t8 C0 P/ j
单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。

当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。

代码展示

1. class Solution {
   
2.     public int maxSumMinProduct(int[] nums) {
   : T, ^0 E7 W( Z- X# F/ T
3.         int n = nums.length;
   
4.         long[] preSum = new long[n + 1];
   0 b. }4 {$ O3 f7 g' {" `, O
5.         for (int i = 1; i <= n; ++i) {
   $ {, h& K- c$ L- S9 q3 q
6.             preSum = preSum[i - 1] + nums[i - 1];
   * s: Q! Z7 J2 T: u' p( F/ B2 _
7.         }
   4 V( e0 ~& Z! u" G
8. 
   
9.         int[] l = new int[n];
   
10.         int[] r = new int[n];
    
11.         Arrays.fill(r, n - 1);
    
12. 
    " E% w1 k. e! h. K0 t
13.         LinkedList<Integer> stack = new LinkedList<>();
    0 @. Q6 _( S3 c0 }: B7 Y3 d
14.         for (int i = 0; i < n; i++) {
    8 W/ B! {6 u1 R& R$ V7 S  d# j
15.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    % p  ?( C) M# ?1 Q- E/ V# w* I
16.                 r[stack.pollFirst()] = i - 1;
    
17.             }
    5 l) U4 ]/ N! a: z; W0 p7 `& G
18.             stack.addFirst(i);
    % L0 u  j  q& g7 _
19.         }
    
20.         stack = new LinkedList<>();
    7 V, q, u1 ?/ F% [1 O
21.         for (int i = n - 1; i >= 0; i--) {
    % u  U$ F* X' |! N1 c
22.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    + G% L3 H1 u* g8 U+ `2 d* j$ b
23.                 l[stack.pollFirst()] = i + 1;
    ! p2 v' @7 [( [5 A! ^
24.             }
    ; }* y1 e# D2 [$ {0 J2 W
25.             stack.addFirst(i);
    
26.         }
    
27. 
    
28.         long res = 0;
    5 N( n/ ^" c% C; o! }+ m8 d
29.         for (int i = 0; i < n; i++) {
    4 R& [, h- P$ ~9 m3 R# N; v5 M
30.             res = Math.max(res, (preSum[r + 1] - preSum[l]) * nums);
    & L) ~$ w& [  F) R7 S
31.         }
    2 s2 ]; i4 |( A4 ]+ o8 `
32. 
    # u5 P5 H% u* y
33.         return (int) (res % 1000000007L);
    
34.     }
    
35. }

复制代码

2 o2 @8 m0 D1 W8 f. X/ h/ I. V$ |& ONo.4 有向图中最大颜色值
* I0 D3 X2 r+ j
解题思路

! ]4 _' Z% u: C# ?9 G  d先判断图中是否有环，有环直接返回 -1.

无环的话则使用动态规划求解。
+ R9 I, ?$ b! r' q3 M2 Q
/ l1 ^; B+ N9 T; i: B$ M* s' d代码展示
: M2 i4 Z- E6 ~( b

1. class Solution {
   
2.     public int largestPathValue(String colors, int[][] edges) {
   
3.         // 建图
   
4.         int n = colors.length();
   
5.         Node[] nodes = new Node[n];
   
6.         for (int i = 0; i < n; i++) {
   
7.             nodes = new Node();
   * G/ S& _% i/ M/ O# i& v" a
8.         }
   
9.         for (int[] e : edges) {
   
10.             nodes[e[0]].nei.add(nodes[e[1]]);
    ) j* |" n/ \  v: g. j; h
11.         }
    & }' H1 ]1 A* h) k
12.         // 判环
    ( {1 f  _& ^* t( d, h1 v
13.         for (Node node : nodes) {
    : V) u2 g; x. z1 W; W- Z0 v
14.             if (findCircle(node)) {
    
15.                 return -1;
    3 P1 R+ P" j" Y8 x/ {2 i$ ?6 D' b1 v
16.             }
    8 f% y3 t0 T* O8 R$ S0 o) n
17.         }
    1 |/ O; @2 s$ Y7 R. u3 j
18.         // 动态规划
    , \; l* _  C; y5 y% b' A
19.         int best = 0;
    
20.         for (int i = 'a'; i <= 'z'; i++) {
    / o- Q  J$ g; d7 G2 k
21.             for (int j = 0; j < n; j++) {
    
22.                 nodes[j].dp = -1;
    
23.                 nodes[j].val = colors.charAt(j) == i ? 1 : 0;
    
24.             }
    
25.             for (int j = 0; j < n; j++) {
    $ l# B' f. H) \% p
26.                 best = Math.max(best, dp(nodes[j]));
    
27.             }
    $ L7 B9 \0 A3 _8 B4 s9 M
28.         }
    
29.         return best;
    
30.     }
    
31. 
    3 m9 S( L/ L, h. W8 ]6 _( F: d# `
32.     public int dp(Node cur) {
    
33.         if (cur.dp == -1) {
    
34.             cur.dp = 0;
    % b9 i# X, L4 R  s
35.             for (Node node : cur.nei) {
    ! t% Y  l% Q9 k( {+ R1 o3 T1 _
36.                 cur.dp = Math.max(cur.dp, dp(node));
    
37.             }
    ( L; i) ~  O4 S+ l! S
38.             cur.dp += cur.val;
    : L0 B: E& }& V" q/ W
39.         }
    " x* @2 X; T6 _5 W  K: o8 B- i
40.         return cur.dp;
    7 B/ N( {: L  K! M/ {+ m
41.     }
    
42. 
    
43.     // 精简版的 Tarjan 算法：
    
44.     // 仅用作判环，而无需求出强连通分量
    $ a  m1 z) Q5 _
45.     // 所以并不需要真正使用栈，只需要一个标志位即可
    
46.     boolean findCircle(Node cur) {
    % x# T7 W$ {2 i/ \2 ^  U
47.         if (cur.vis) {
    
48.             return cur.stk;
    
49.         }
    
50.         cur.vis = cur.stk = true;
    , h- F9 b, h/ j
51.         for (Node node : cur.nei) {
    5 {  O: C7 g$ ~  `  M
52.             if (findCircle(node)) {
    
53.                 return true;
    
54.             }
    
55.         }
    
56.         cur.stk = false;
    
57.         return false;
    
58.     }
    
59. }
    9 x% A. |8 e/ @
60. 
    + p/ W! `6 U# g; E& f
61. class Node {
    . T% Y8 {9 \( }( q- X% m8 V" X
62.     int val, dp;
    
63.     boolean vis, stk;
    8 k+ t5 a% |5 q3 v% ~9 N
64.     List<Node> nei;
    
65. 
    
66.     Node() {
    7 z+ z6 u5 T/ I& n$ O, c3 P* X
67.         dp = -1;
    . S' V& s9 S- v
68.         nei = new ArrayList<>();
    
69.     }
    
70. }

复制代码

# G9 k9 x" F  L2 j% K( M
9 ?. v. h  I5 F& z