LeetCode Weekly Contest 240解题报告

No.1 人口最多的年份

解题思路
, ^, u+ H4 i$ ~; i5 a6 o$ M
数据范围比较小，直接枚举统计即可。

代码展示

1. 
   
2. class Solution {
     w/ T+ X: o* h4 a  ~: f* h
3.     public int maximumPopulation(int[][] logs) {
   * w* q' ?8 F( \8 ~
4.         int[] population = new int[2051];
   * d, A: a* E# w4 ^
5.         for (var log : logs) {
   ) X8 w& ~6 s3 U/ k% f* |
6.             for (int i = log[0]; i < log[1]; i++) {
   
7.                 population++;
   / B- w( E' M1 |+ O4 C$ Z, G
8.             }
   
9.         }
   
10.         int res = 1950;
    3 L) Q  ]- G$ G/ H" w7 e/ M  p
11.         for (int i = 1951; i <= 2050; i++) {
    / J/ |& u' I5 P& \0 }3 f' I- a* W
12.             if (population > population[res]) {
    
13.                 res = i;
    7 a' J$ A  l9 h" `
14.             }
    
15.         }
    
16.         return res;
    
17.     }
    9 P9 r* l' V" y; [6 }. s
18. }

复制代码

. }. v; i" J& b) ^  X; fNo.2下标对中的最大距离
, m0 b# G; [# @7 ?9 F
4 `% E0 [7 b; }解题思路
& A- ]9 f0 S: P* D  ?1 d
输入的两个数组都是单调的，可以使用双指针。

% q: Y/ O* t6 `) ~: n3 Q( U2 c3 v代码展示

1. class Solution {
   
2.     public int maxDistance(int[] nums1, int[] nums2) {
   % j6 \1 J. I+ C! H: [2 F, w
3.         int n = nums1.length, m = nums2.length;
   . @2 b$ ]9 p2 G# ^  R
4.         int res = 0;
   " n" T- R! T3 m$ A6 i0 ?1 h
5.         for (int i = 0, j = -1; i < n; i++) {
   
6.             while (j + 1 < m && nums1 <= nums2[j + 1]) {
   & m8 P# A$ M6 x' v0 o4 m
7.                 j++;
   7 a: x& r- d" N; E
8.             }
   
9.             res = Math.max(res, j - i);
   6 p% d' `. i7 y3 {7 ], I9 @$ g
10.         }
    
11.         return res;
    ( |9 ?& g% h0 [. s
12.     }
    
13. }

复制代码

No.3 子数组最小乘积的最大值

% R; e& s( T" r0 r解题思路
0 M( \/ R1 G! }" c9 \" j
单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。

7 M( t* v5 E0 o当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。
! G  z( {( I# F2 p1 [
& ?  w- j- a- b: V代码展示
  Q: q9 E! u/ U  B! j

1. class Solution {
   : H: p( Y1 @, i, E3 i
2.     public int maxSumMinProduct(int[] nums) {
   : v9 S8 u& @+ f% }: p& c
3.         int n = nums.length;
   ! H4 x+ }7 b( _$ w
4.         long[] preSum = new long[n + 1];
   0 K8 z/ j5 E  d: H, O6 P* Y  H8 e
5.         for (int i = 1; i <= n; ++i) {
   
6.             preSum = preSum[i - 1] + nums[i - 1];
   ! @0 a2 {4 ?/ k, n6 B6 `! H3 W" R& p
7.         }
   
8. 
   
9.         int[] l = new int[n];
   
10.         int[] r = new int[n];
    * F1 j  m2 ^% V) k7 z0 Y
11.         Arrays.fill(r, n - 1);
    5 q8 u) ^" o& d' A) q6 c1 p4 U
12. 
    ( B1 q/ T3 N1 B% `
13.         LinkedList<Integer> stack = new LinkedList<>();
    / {7 h/ @! k3 a/ D3 F
14.         for (int i = 0; i < n; i++) {
    
15.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    ; [* Y5 i6 p4 q1 Q' y3 |
16.                 r[stack.pollFirst()] = i - 1;
    
17.             }
    
18.             stack.addFirst(i);
    9 p" s% g: x" Z6 Q  X6 g% ]
19.         }
    
20.         stack = new LinkedList<>();
    
21.         for (int i = n - 1; i >= 0; i--) {
    
22.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    
23.                 l[stack.pollFirst()] = i + 1;
    
24.             }
    
25.             stack.addFirst(i);
    
26.         }
    3 x  f' n" \6 |
27. 
    ( a2 E. t+ D' D3 o0 h
28.         long res = 0;
    
29.         for (int i = 0; i < n; i++) {
    
30.             res = Math.max(res, (preSum[r + 1] - preSum[l]) * nums);
    # T9 S- ^$ K/ ]& p6 m3 b& O; w1 \) B
31.         }
    9 r+ @# V: m9 _5 e
32. 
    
33.         return (int) (res % 1000000007L);
    
34.     }
    5 o" x. c& D5 Y' E8 m8 {/ b1 q$ j
35. }

复制代码

No.4 有向图中最大颜色值
9 i$ d  S* a( ?2 }3 ?. ?; v* J/ s2 G
; _4 x# x8 {5 S) k' y2 k8 @解题思路
  ?* e# C" _* D* P$ k$ u
先判断图中是否有环，有环直接返回 -1.
8 G2 p, Y$ M$ F! e( ?2 \3 g: s2 a
无环的话则使用动态规划求解。
$ x: t% Y2 _' M2 M+ f; v$ z
0 [7 ]8 E# B: L0 R/ b4 p代码展示

! j- L7 Z! x5 X

1. class Solution {
   
2.     public int largestPathValue(String colors, int[][] edges) {
   % @! e3 s0 w: Q; e
3.         // 建图
   
4.         int n = colors.length();
   + O) K) \( h# R9 p* u+ l2 T  k0 X4 l
5.         Node[] nodes = new Node[n];
   
6.         for (int i = 0; i < n; i++) {
   
7.             nodes = new Node();
   
8.         }
   " u' n/ g. ^- g" Y/ R. q, H
9.         for (int[] e : edges) {
   8 C1 l8 K) z% g, w4 }* p
10.             nodes[e[0]].nei.add(nodes[e[1]]);
    
11.         }
    0 y2 [' g& \4 D' r
12.         // 判环
    
13.         for (Node node : nodes) {
    ' e# ?4 A6 V5 ]7 I8 A6 k
14.             if (findCircle(node)) {
    & n6 Z- A, p/ D* ^7 x/ N8 P
15.                 return -1;
    ! y9 H8 d. `9 Q. N2 a
16.             }
    
17.         }
    6 @0 a& u7 N1 L" Q& c) z5 c, D- O$ K
18.         // 动态规划
    
19.         int best = 0;
    " b; k% G8 h7 h
20.         for (int i = 'a'; i <= 'z'; i++) {
    * q2 X6 {4 Y" c6 d
21.             for (int j = 0; j < n; j++) {
    
22.                 nodes[j].dp = -1;
    ) l& E6 i' P  ~; i# F; e( R
23.                 nodes[j].val = colors.charAt(j) == i ? 1 : 0;
    5 ]! Z2 @0 {/ n' v: G4 y- D
24.             }
    
25.             for (int j = 0; j < n; j++) {
    
26.                 best = Math.max(best, dp(nodes[j]));
    
27.             }
    
28.         }
    
29.         return best;
    8 f( _1 @5 m$ R, e5 E# }
30.     }
      M1 b/ N- a* p- K; h( @0 K
31. 
    + s  H  V2 _, k% X7 B4 W* k
32.     public int dp(Node cur) {
    
33.         if (cur.dp == -1) {
    , m1 o& D- ?+ O8 K
34.             cur.dp = 0;
    * h1 e+ Z" H9 O3 }$ v& f& u
35.             for (Node node : cur.nei) {
    
36.                 cur.dp = Math.max(cur.dp, dp(node));
    $ X% F+ [2 X. }" l/ M# r
37.             }
    
38.             cur.dp += cur.val;
    5 v$ d5 L7 o7 Z/ J8 s) |9 P& q; G3 I
39.         }
    7 z) _6 {( E1 U9 @
40.         return cur.dp;
    
41.     }
    
42. 
    
43.     // 精简版的 Tarjan 算法：
    ; u7 ^$ s/ m* n$ {! C- l
44.     // 仅用作判环，而无需求出强连通分量
    
45.     // 所以并不需要真正使用栈，只需要一个标志位即可
    . J# o# x2 w2 i
46.     boolean findCircle(Node cur) {
    . c- g& B  E& g8 v+ B8 V% s
47.         if (cur.vis) {
    9 ?8 y! Q7 r% T! e1 }
48.             return cur.stk;
    2 G- e( ~9 m  ^: j" q
49.         }
    & E& L% L* |, z- w. Z# t
50.         cur.vis = cur.stk = true;
      ]3 H& O% @1 k0 U5 p3 K5 `# O, @
51.         for (Node node : cur.nei) {
    
52.             if (findCircle(node)) {
    : o. b# E: v% M0 P: \# D! t
53.                 return true;
    " Y5 n8 ^" W$ a8 G1 W5 @
54.             }
    
55.         }
    
56.         cur.stk = false;
    
57.         return false;
    - }9 X  }+ @9 }% L
58.     }
    5 D: a5 C& j1 A" ~
59. }
    
60. 
    4 y. Z* R6 f/ d& N
61. class Node {
    
62.     int val, dp;
    
63.     boolean vis, stk;
    4 J9 |/ o* V& k0 j
64.     List<Node> nei;
    7 y! j# ~1 s, w6 [3 }3 F1 _1 Z% e
65. 
    
66.     Node() {
    
67.         dp = -1;
    
68.         nei = new ArrayList<>();
    
69.     }
    7 {: b& U6 a( T- l! a) z
70. }

复制代码

7 [# I/ |5 N# V$ H+ i* d" W