LeetCode Weekly Contest 240解题报告

No.1 人口最多的年份
# V# G1 M  V  M7 `
) f6 `/ S- _( k2 K2 F解题思路
* N% Y: B  d4 ]! @. `* X' }
9 t( ?/ ~- I5 Q1 r0 K1 C数据范围比较小，直接枚举统计即可。

% p! J9 g) k. Q$ d7 \5 m代码展示
* b! d3 C4 H; a) h

1. 
   
2. class Solution {
   ( R- t* h" ]' r- h, i$ G$ @$ \
3.     public int maximumPopulation(int[][] logs) {
   8 x' N- k' u5 X3 ?+ a
4.         int[] population = new int[2051];
   
5.         for (var log : logs) {
   2 N* g  ], q1 y2 O% l$ U
6.             for (int i = log[0]; i < log[1]; i++) {
   0 n7 ~' f7 y) ]2 }" X
7.                 population++;
   ! s  l6 P. D) f! s
8.             }
   
9.         }
   
10.         int res = 1950;
    " f9 T, t) s! H/ P! [, F0 j
11.         for (int i = 1951; i <= 2050; i++) {
    
12.             if (population > population[res]) {
    : n3 x7 n$ m) q- }; g
13.                 res = i;
    % m3 v: H4 o9 ]* d3 e+ k
14.             }
    
15.         }
    # ]% c( J, f# |5 V
16.         return res;
    / Y/ P$ V$ [) {' ~  u# l
17.     }
    
18. }

复制代码

; ]1 c; }2 m5 p, e& ]# i- a0 cNo.2下标对中的最大距离

解题思路
0 J& T$ M9 O. R9 W! W0 `
输入的两个数组都是单调的，可以使用双指针。
  x: ^$ G0 ?# F9 y8 \! y
代码展示
- l% U6 s! `( Q  f1 y1 N- B' p! v

1. class Solution {
   ! V$ |/ H9 K+ n0 p
2.     public int maxDistance(int[] nums1, int[] nums2) {
   * n4 K4 U6 F, L
3.         int n = nums1.length, m = nums2.length;
   0 X6 W& @! G5 k% {/ \' k. o6 g' m
4.         int res = 0;
   % b9 G3 V4 y, K4 j* |
5.         for (int i = 0, j = -1; i < n; i++) {
   
6.             while (j + 1 < m && nums1 <= nums2[j + 1]) {
   
7.                 j++;
   ' g# w8 T- I- y! A- C7 N
8.             }
   " L7 x% L& k( H  y' d8 M8 k
9.             res = Math.max(res, j - i);
   1 p! S6 N2 N$ ]( R  C' j* G
10.         }
    : O8 ~/ j) I2 a5 E
11.         return res;
    
12.     }
    & O0 M. C7 L0 z% n: U0 L7 {
13. }

复制代码

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

解题思路

8 @3 v: U; h* ]. i单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。
2 I; P6 ]: \% Z: D" B: D% F( H
+ `/ c. n2 e& {( X9 N+ ~当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。

代码展示

1. class Solution {
   + e6 V" Z6 H+ _. H& h
2.     public int maxSumMinProduct(int[] nums) {
   
3.         int n = nums.length;
   
4.         long[] preSum = new long[n + 1];
   
5.         for (int i = 1; i <= n; ++i) {
   5 J5 G! b5 W- ?5 a  }
6.             preSum = preSum[i - 1] + nums[i - 1];
   
7.         }
   / g. u; w( {  ^: e0 a7 e1 S7 w
8. 
     y2 K8 w2 t- D7 W( d9 ^# R
9.         int[] l = new int[n];
   
10.         int[] r = new int[n];
    4 D" X( _) ?( o+ h2 h: T9 g
11.         Arrays.fill(r, n - 1);
    
12. 
    
13.         LinkedList<Integer> stack = new LinkedList<>();
    1 l! \8 J  Z' q+ k: e/ H1 q
14.         for (int i = 0; i < n; i++) {
    * R8 w+ S  {# f9 Y
15.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    
16.                 r[stack.pollFirst()] = i - 1;
    
17.             }
    " N" I! E$ j5 N3 j& q2 f" }* R; W
18.             stack.addFirst(i);
    3 O4 t5 G- l& l6 }$ x5 j, F
19.         }
    7 V6 i5 a3 I8 V; e
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.         }
    
27. 
    
28.         long res = 0;
    6 j3 Z  C: P# b, x$ L( k
29.         for (int i = 0; i < n; i++) {
    / W( K6 R* `4 r( H  e) q
30.             res = Math.max(res, (preSum[r + 1] - preSum[l]) * nums);
    
31.         }
    
32. 
    6 ^) z8 S. w5 v: c5 k
33.         return (int) (res % 1000000007L);
    
34.     }
    # {- J  P+ H" O
35. }

复制代码

No.4 有向图中最大颜色值

解题思路
8 {+ D8 U" O6 M, S; i. R" Y; P
先判断图中是否有环，有环直接返回 -1.
( `8 t) C( i9 r. k# W
无环的话则使用动态规划求解。
  C  `6 x3 _; [7 M% x
' c! P$ b9 L6 x& g5 u5 D代码展示

; h- b: t' ]. w% z

1. class Solution {
   
2.     public int largestPathValue(String colors, int[][] edges) {
   
3.         // 建图
   
4.         int n = colors.length();
   
5.         Node[] nodes = new Node[n];
   7 |# Y  T/ Q1 A
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]]);
    , R& a" l( A+ L. l) M4 f1 D3 @8 r
11.         }
    7 A% e" U0 c2 q4 U# {
12.         // 判环
    : `% |% n: l: o5 M# u" ?5 d
13.         for (Node node : nodes) {
    
14.             if (findCircle(node)) {
    , i! e" S* j( J' ^$ ?0 b
15.                 return -1;
    " j6 Y5 H" a9 ]/ x1 c
16.             }
    ! V8 ]: f6 ~( V( V% C* a( R
17.         }
    0 b( k; P% J( T0 T9 ~0 z
18.         // 动态规划
    * U+ R5 h# Q5 z' R# @3 Q, p
19.         int best = 0;
    
20.         for (int i = 'a'; i <= 'z'; i++) {
    
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++) {
    
26.                 best = Math.max(best, dp(nodes[j]));
    
27.             }
    
28.         }
    
29.         return best;
    ) h. J" h5 f: P' y6 |  F6 s
30.     }
    * t3 P+ R( t( T: T3 A9 h. B& B
31. 
    ' ]6 k0 n/ E, G1 W5 _$ W) |
32.     public int dp(Node cur) {
    
33.         if (cur.dp == -1) {
    ' i. y# y5 b3 _* G
34.             cur.dp = 0;
    8 q( m' B+ E" N& C6 r2 o' M
35.             for (Node node : cur.nei) {
    ( @* o7 M# m! H) N' @
36.                 cur.dp = Math.max(cur.dp, dp(node));
      j' B1 M+ O' c5 a4 [5 R7 _& F, e
37.             }
    / _7 J& J9 f. k4 e) p
38.             cur.dp += cur.val;
    
39.         }
    
40.         return cur.dp;
    
41.     }
    , A  i3 ^4 R' k1 X" L# h' E
42. 
    3 z3 U' q0 Z, J
43.     // 精简版的 Tarjan 算法：
    
44.     // 仅用作判环，而无需求出强连通分量
    , G" A, P/ }9 h' I8 `* n
45.     // 所以并不需要真正使用栈，只需要一个标志位即可
    
46.     boolean findCircle(Node cur) {
    . x% c+ G5 L1 \# P
47.         if (cur.vis) {
    3 h+ ~! [9 e) ?# l  }' a3 R  g
48.             return cur.stk;
    7 f3 r; N+ A0 S+ c: n
49.         }
    
50.         cur.vis = cur.stk = true;
    ( P4 C0 f' M7 R# {7 D. M& N
51.         for (Node node : cur.nei) {
    
52.             if (findCircle(node)) {
    8 u) x4 w2 Z( K3 a- V1 m. }
53.                 return true;
      h4 r6 Y) @! K; x5 f2 h8 J
54.             }
    6 |; J7 B( j1 O1 D; @- O( O% v
55.         }
    - Z; K8 C! f- V, d& M) c9 }; \4 T
56.         cur.stk = false;
    : A0 e; V8 `( S# p& J  A3 a/ \
57.         return false;
    " o; U) P  @0 G. {7 ^$ o
58.     }
    
59. }
    
60. 
    " `* k* {; K9 B. E
61. class Node {
    
62.     int val, dp;
    
63.     boolean vis, stk;
    - ^$ Q+ X" k1 a% |& V7 c
64.     List<Node> nei;
    $ O1 G. W, l2 L# u: @3 J
65. 
    
66.     Node() {
    
67.         dp = -1;
    " V6 l7 e& H9 w& k# N6 ~
68.         nei = new ArrayList<>();
    
69.     }
    
70. }

复制代码

2 M% D$ b5 f3 \) }; K
8 a. I: ^1 r5 {5 p( t