LeetCode Weekly Contest 240解题报告

No.1 人口最多的年份
& b7 g, R9 c, E/ O
解题思路
- p) G4 G0 H. C( t' v
数据范围比较小，直接枚举统计即可。
, o1 H0 j5 V0 n. j2 n' C3 K
( W0 f5 J6 u; z$ M代码展示
% _' a6 z# L% u! \

1. 
   
2. class Solution {
     ^2 @. v' O2 ]$ u4 j3 z. g
3.     public int maximumPopulation(int[][] logs) {
   ( t3 o  V6 N! n+ {1 ~9 G
4.         int[] population = new int[2051];
   * W. {6 K* O+ q6 d. u4 T& A
5.         for (var log : logs) {
   # Y7 E. o8 c* z% ]3 Q2 P% o* x! N4 Q
6.             for (int i = log[0]; i < log[1]; i++) {
   
7.                 population++;
   ; Q( N; U8 X/ _
8.             }
   
9.         }
   / T- q* i: ?( \; f
10.         int res = 1950;
    
11.         for (int i = 1951; i <= 2050; i++) {
    
12.             if (population > population[res]) {
    4 v# J1 a) k! x; E( X
13.                 res = i;
    , ~0 }/ F# z8 W* \) A  \0 n( m2 r
14.             }
    
15.         }
    8 z2 `- W! d, m" v* \( c
16.         return res;
    9 A, g: d8 G8 Y( v
17.     }
    . V# q( j# B+ k) w, J$ \
18. }

复制代码

) z, a5 @4 H. z% a- fNo.2下标对中的最大距离

解题思路
8 T" a: ]4 O+ U. J( D1 Z6 J1 ?
# Q* L0 x) p4 \9 i输入的两个数组都是单调的，可以使用双指针。

代码展示

1. class Solution {
   
2.     public int maxDistance(int[] nums1, int[] nums2) {
   9 Q1 {+ u5 ~9 }6 x
3.         int n = nums1.length, m = nums2.length;
   
4.         int res = 0;
     o( N- z  f+ e+ O
5.         for (int i = 0, j = -1; i < n; i++) {
   , l, a6 o. u3 b
6.             while (j + 1 < m && nums1 <= nums2[j + 1]) {
   : d1 L1 @  v* N. l
7.                 j++;
   7 c. j- c! ?+ ^  c+ e
8.             }
   $ z/ D) Q9 b  T6 j
9.             res = Math.max(res, j - i);
   0 p+ s( u" V+ K
10.         }
    
11.         return res;
    
12.     }
    ' r3 O. c% R& [. q
13. }

复制代码

. @9 H6 P. E+ ^4 X$ ^# u  oNo.3 子数组最小乘积的最大值
% M6 |  W) F7 p" @4 N
解题思路

单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。
' n% S! t6 h2 y% ~
7 H1 S( t0 @% q" t2 z当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。

, ]& U; o( ^1 x- W) y& |0 t. `代码展示

1. class Solution {
   9 X  t6 U$ n" b" h- u! d
2.     public int maxSumMinProduct(int[] nums) {
   3 c* J! y& \% ]7 }. s
3.         int n = nums.length;
   
4.         long[] preSum = new long[n + 1];
   6 E. m4 r1 V. F
5.         for (int i = 1; i <= n; ++i) {
   
6.             preSum = preSum[i - 1] + nums[i - 1];
   
7.         }
   ( J0 n' U' C. X8 x) Y
8. 
   
9.         int[] l = new int[n];
   1 m+ g- s( ?0 g
10.         int[] r = new int[n];
    ( {; m8 t0 c4 Q! c3 L3 q! x
11.         Arrays.fill(r, n - 1);
    
12. 
    " Q' C3 V* F4 Z0 H
13.         LinkedList<Integer> stack = new LinkedList<>();
    $ G* ?4 o0 r, p( L% W/ ~7 ]( Q2 U4 j" Z
14.         for (int i = 0; i < n; i++) {
    ( }, T* j1 C$ z! w" ?- P$ b
15.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    
16.                 r[stack.pollFirst()] = i - 1;
    
17.             }
    
18.             stack.addFirst(i);
    
19.         }
    
20.         stack = new LinkedList<>();
    % ~8 c) s% Z! U9 r1 Z
21.         for (int i = n - 1; i >= 0; i--) {
    $ G1 R/ |3 w& J) b! }! ]) c
22.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    
23.                 l[stack.pollFirst()] = i + 1;
    
24.             }
    
25.             stack.addFirst(i);
    
26.         }
    
27. 
    
28.         long res = 0;
    
29.         for (int i = 0; i < n; i++) {
    
30.             res = Math.max(res, (preSum[r + 1] - preSum[l]) * nums);
    / [5 d- S6 T8 Y. t& M
31.         }
    
32. 
    
33.         return (int) (res % 1000000007L);
    
34.     }
    - T& r8 l* g! [# F
35. }

复制代码

0 P$ `  j5 @2 l# H0 YNo.4 有向图中最大颜色值
& p$ F  l% J0 m- o+ g4 j- N. l
7 T# [$ w" L; H9 Q4 e; a解题思路

先判断图中是否有环，有环直接返回 -1.
$ v' N' W7 F' J4 f
& `8 z! v6 s1 r无环的话则使用动态规划求解。

+ U# b) ^7 {" w0 R, o代码展示

1. class Solution {
   - ]/ u8 v, v8 r$ c- a
2.     public int largestPathValue(String colors, int[][] edges) {
   
3.         // 建图
   3 O1 }+ C% V' n1 w; F' U
4.         int n = colors.length();
   
5.         Node[] nodes = new Node[n];
   ! B0 w5 E, `' s. J( a: I- u( g; T7 Z
6.         for (int i = 0; i < n; i++) {
   
7.             nodes = new Node();
   
8.         }
   
9.         for (int[] e : edges) {
   
10.             nodes[e[0]].nei.add(nodes[e[1]]);
    
11.         }
    2 l) I% ]+ J. b7 h
12.         // 判环
    ( c( ]' R) A% _! L" f5 g/ O0 ^
13.         for (Node node : nodes) {
    * Q2 \: `# b" Y/ u1 s# W
14.             if (findCircle(node)) {
    
15.                 return -1;
    
16.             }
    - J9 v: t7 C6 q6 }* o
17.         }
    ( K9 I/ |3 Q5 D
18.         // 动态规划
    9 h. S2 l' c0 b' g$ J
19.         int best = 0;
    
20.         for (int i = 'a'; i <= 'z'; i++) {
    + l" y/ P7 @, R) h
21.             for (int j = 0; j < n; j++) {
    
22.                 nodes[j].dp = -1;
    3 c$ E2 Q7 t; V# k/ m; o8 D' e
23.                 nodes[j].val = colors.charAt(j) == i ? 1 : 0;
      t$ h5 e4 ~% w' o2 O
24.             }
    
25.             for (int j = 0; j < n; j++) {
    ! B( {$ W9 Q! Z0 E+ p1 W/ C
26.                 best = Math.max(best, dp(nodes[j]));
    
27.             }
    
28.         }
    
29.         return best;
    1 z& o: [/ {3 n0 S- S8 b/ Z  f  X
30.     }
    ) Z% R+ V7 D8 f7 r( p
31. 
    
32.     public int dp(Node cur) {
    % g$ r1 J( Y: g2 E1 l
33.         if (cur.dp == -1) {
    
34.             cur.dp = 0;
    
35.             for (Node node : cur.nei) {
    
36.                 cur.dp = Math.max(cur.dp, dp(node));
    
37.             }
    
38.             cur.dp += cur.val;
    % i& C9 u. M; O3 d& G: a
39.         }
    
40.         return cur.dp;
    + F2 n* o# S3 Y8 U0 X# N% U
41.     }
    + w- |: C! z; u$ V
42. 
    / D" Y# Z- G/ t1 d! Q) u( L
43.     // 精简版的 Tarjan 算法：
    
44.     // 仅用作判环，而无需求出强连通分量
    
45.     // 所以并不需要真正使用栈，只需要一个标志位即可
    
46.     boolean findCircle(Node cur) {
    
47.         if (cur.vis) {
    
48.             return cur.stk;
      ]0 b0 M( R- M+ A
49.         }
    . j* \5 [2 y4 G2 Y+ O
50.         cur.vis = cur.stk = true;
    
51.         for (Node node : cur.nei) {
    
52.             if (findCircle(node)) {
    ) U& T& r% `0 Q! r  ~+ I0 q
53.                 return true;
    8 b# Z3 V* _, S1 S, s% P
54.             }
    & _8 x) R) Y9 V+ ?4 ?5 J
55.         }
    0 c' Q- i! |' C! H1 C) H4 m* N) ?
56.         cur.stk = false;
    
57.         return false;
    & B/ d' j( F+ k6 C
58.     }
    
59. }
    ! w: @2 K- ?! O& @- j1 `$ p
60. 
    ) [# z3 f) A1 l, t6 f8 u
61. class Node {
      t2 f$ r+ c0 A" K: ^2 J
62.     int val, dp;
    ! h& D  ?9 w% |5 \9 J
63.     boolean vis, stk;
    
64.     List<Node> nei;
    
65. 
    
66.     Node() {
    ) k0 t  I# u. E! ^4 \1 J% U
67.         dp = -1;
    + h: N3 n5 ~; X# W6 b8 |0 u& m) K
68.         nei = new ArrayList<>();
    
69.     }
    ) H" J4 c4 q' b$ U' s9 w3 Z
70. }

复制代码

" @7 D" Q7 x+ x2 z7 r- b