LeetCode Weekly Contest 240解题报告

No.1 人口最多的年份
9 n0 M/ G2 l: H3 _
解题思路

数据范围比较小，直接枚举统计即可。
% R8 j$ Z, p' m7 i0 G, A
# b) ^; S8 x. m, L7 J1 ~代码展示

1. 
   $ B) V: O4 u5 I; Q; [
2. class Solution {
   
3.     public int maximumPopulation(int[][] logs) {
   
4.         int[] population = new int[2051];
   
5.         for (var log : logs) {
   
6.             for (int i = log[0]; i < log[1]; i++) {
   % s% z8 O) ~5 l( a4 [: b
7.                 population++;
   ; G) R' }' A5 j
8.             }
   
9.         }
   . H7 B& j7 _  G; o) y! X, m- [
10.         int res = 1950;
    
11.         for (int i = 1951; i <= 2050; i++) {
    * N! E" R9 @( N
12.             if (population > population[res]) {
    1 p5 }) H. X5 v3 L; I+ W5 D$ C0 k
13.                 res = i;
    & Y2 b. H! |5 a5 F+ \$ ]1 x* s+ \: s
14.             }
    " R7 h) G3 Y: m7 U" \- u
15.         }
    
16.         return res;
    
17.     }
    
18. }

复制代码

) ?4 ~, b. K6 r8 o
' `5 i! o9 n, }( f- b& j; ^No.2下标对中的最大距离

解题思路

* l2 \- o' ~( ~3 q% O! `* W: R输入的两个数组都是单调的，可以使用双指针。

代码展示

1. class Solution {
   8 W, K3 T/ S; i$ Y: u( Z3 }
2.     public int maxDistance(int[] nums1, int[] nums2) {
   
3.         int n = nums1.length, m = nums2.length;
   
4.         int res = 0;
   . N$ n- M$ }1 N5 S( ]* X; B1 y
5.         for (int i = 0, j = -1; i < n; i++) {
   2 m' [$ \1 F0 K( j. w! F
6.             while (j + 1 < m && nums1 <= nums2[j + 1]) {
   . f- F$ S4 s# [
7.                 j++;
   - B9 T/ Q+ U; n% l; H
8.             }
   
9.             res = Math.max(res, j - i);
   
10.         }
    
11.         return res;
    
12.     }
    % j' g1 l! X" ~+ y9 k5 W0 A
13. }

复制代码

No.3 子数组最小乘积的最大值
  y+ ?% P' E/ w9 `2 ^
解题思路

单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。
# S( M: a  j1 U5 u( v
当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。

代码展示
" T7 j* s) F# D. I3 c# N

1. class Solution {
   5 M( i- S$ h" p! Z1 [1 a" R
2.     public int maxSumMinProduct(int[] nums) {
   6 l( b0 _5 H% T% g
3.         int n = nums.length;
   
4.         long[] preSum = new long[n + 1];
   ) f7 S0 Z3 r* \: ?  |
5.         for (int i = 1; i <= n; ++i) {
   % M0 J- Z7 V- n
6.             preSum = preSum[i - 1] + nums[i - 1];
   
7.         }
   
8. 
   " I& G7 a0 L1 l9 [: Y8 Y
9.         int[] l = new int[n];
   
10.         int[] r = new int[n];
    
11.         Arrays.fill(r, n - 1);
    : a1 p  w% B: A- U) G% Q
12. 
    
13.         LinkedList<Integer> stack = new LinkedList<>();
    
14.         for (int i = 0; i < n; i++) {
    
15.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    
16.                 r[stack.pollFirst()] = i - 1;
    
17.             }
    
18.             stack.addFirst(i);
    
19.         }
    
20.         stack = new LinkedList<>();
    # }+ h7 l1 O; R$ O, a% o  C
21.         for (int i = n - 1; i >= 0; i--) {
    0 `' W# ]) E; _# A1 c
22.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    8 f; a0 E' h5 b% r% d6 {
23.                 l[stack.pollFirst()] = i + 1;
    6 j3 I) a( T# b8 s
24.             }
    5 }& \* v$ g" W' Z! S7 q! Q# d* r  c5 g
25.             stack.addFirst(i);
    7 q! p& E) c! |0 G+ u
26.         }
    6 I" J: v, }3 ]4 W% U
27. 
    
28.         long res = 0;
    
29.         for (int i = 0; i < n; i++) {
    
30.             res = Math.max(res, (preSum[r + 1] - preSum[l]) * nums);
    
31.         }
    ' ]5 J9 l: \  q$ a. `
32. 
    
33.         return (int) (res % 1000000007L);
    : o8 G9 J, s/ _! }# d  M; t
34.     }
    
35. }

复制代码

No.4 有向图中最大颜色值
/ g: `) P- w8 W+ w: h, ~
: q' F$ Z+ `) e; f' T/ ^: y5 J解题思路
. C( T# S" }! E! @& W. w
先判断图中是否有环，有环直接返回 -1.

1 B2 k4 D8 e7 |1 s3 \( M* t无环的话则使用动态规划求解。
, x6 @& q7 l+ t. X, Q& i6 ?
代码展示

1. class Solution {
     d5 ]% w% ]1 z# \5 o5 s3 g# M6 k
2.     public int largestPathValue(String colors, int[][] edges) {
   
3.         // 建图
   : X, Z$ Q* j1 J+ H
4.         int n = colors.length();
   # f. s" c& L2 K$ l1 J: O
5.         Node[] nodes = new Node[n];
     m4 `' y2 g  S7 W* j, R% [7 d
6.         for (int i = 0; i < n; i++) {
   5 e2 T! l: |% V( r9 X' M* u
7.             nodes = new Node();
   
8.         }
   
9.         for (int[] e : edges) {
   : ?3 J: z) o% B( ?+ U6 j0 e
10.             nodes[e[0]].nei.add(nodes[e[1]]);
    , i9 D  N. m0 j1 _' }( U/ o
11.         }
    4 y1 h$ v' I* v$ J# x$ j; T
12.         // 判环
    
13.         for (Node node : nodes) {
    
14.             if (findCircle(node)) {
    
15.                 return -1;
    " I" L0 T( Z" G1 ?  X& W
16.             }
    
17.         }
    
18.         // 动态规划
    
19.         int best = 0;
    
20.         for (int i = 'a'; i <= 'z'; i++) {
    $ m: ?! m9 K' X8 I
21.             for (int j = 0; j < n; j++) {
      T7 @- z0 q& v! b" c. ?2 P* Z( J
22.                 nodes[j].dp = -1;
    
23.                 nodes[j].val = colors.charAt(j) == i ? 1 : 0;
    : V3 Q$ V5 I. \
24.             }
    
25.             for (int j = 0; j < n; j++) {
    1 x2 G4 w# a. [  e% S7 x$ W
26.                 best = Math.max(best, dp(nodes[j]));
    
27.             }
    
28.         }
    3 G; g- {' T; w: a3 ~9 m
29.         return best;
    % v* W! G- ]5 j' I) M3 Z
30.     }
    8 N+ q3 a( z8 V0 ]+ @  F
31. 
    
32.     public int dp(Node cur) {
    ! x0 h8 ?9 V; _1 m. s, C
33.         if (cur.dp == -1) {
    3 l) Y1 W; c/ F& s; [: ?; s, k& Z4 r
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;
    ' I8 Z6 P! n+ z- _, i6 W8 S% ]
39.         }
    / x1 b9 S; V) V  D+ X5 T- R' V
40.         return cur.dp;
    % A* n5 E/ J$ `& X4 l
41.     }
    ( d2 r6 [4 U7 Q) G0 W* u
42. 
    
43.     // 精简版的 Tarjan 算法：
    
44.     // 仅用作判环，而无需求出强连通分量
    . {4 k. P& {* `
45.     // 所以并不需要真正使用栈，只需要一个标志位即可
    8 n% G& f2 l: [3 E2 R& |
46.     boolean findCircle(Node cur) {
    
47.         if (cur.vis) {
    . G2 q3 u/ x0 L' j  C3 {5 f
48.             return cur.stk;
    5 Q4 o" y6 Y- F0 d
49.         }
    ' m3 K: k; v% b; B$ p5 J
50.         cur.vis = cur.stk = true;
    
51.         for (Node node : cur.nei) {
    
52.             if (findCircle(node)) {
    7 \9 B: v3 w% l7 b. ^; B- i
53.                 return true;
    + A* e6 V/ [! ^& X+ P. F) j1 v
54.             }
    
55.         }
    3 v+ C. e6 S! p1 L% }8 i
56.         cur.stk = false;
    * [, O  l. q+ {" l1 P6 h% u
57.         return false;
    & l+ o3 c' \8 f  q' r. d0 K
58.     }
    
59. }
    $ i7 Q/ O1 j# A
60. 
    " m& V0 [; [: e# B" ~1 E$ K2 M
61. class Node {
    % o' q, `# ~3 T& ?8 h: W5 b; i
62.     int val, dp;
    
63.     boolean vis, stk;
    % C1 K3 k  [/ x
64.     List<Node> nei;
    / h; I* ?5 J0 {; m+ `- v
65. 
    
66.     Node() {
    
67.         dp = -1;
    0 H' G2 _6 Q; `1 a5 I$ ]1 z
68.         nei = new ArrayList<>();
    5 Y$ a; W- T  F5 N0 ^. h
69.     }
    # G, e( j* B- X5 X. _
70. }

复制代码

. a* l; j% C  L& H5 d6 x4 D
' `' M( w1 Y& N* q5 c- Z2 R