LeetCode Weekly Contest 240解题报告

No.1 人口最多的年份
; I- n) @3 G9 H3 m
解题思路

数据范围比较小，直接枚举统计即可。
( V1 }2 W, {% u; w$ `
7 b- d! F* a( d, N1 F& v& E代码展示
  F$ R9 u! C0 q$ A6 j) e* `

1. 
   
2. class Solution {
   
3.     public int maximumPopulation(int[][] logs) {
   
4.         int[] population = new int[2051];
   : s& x8 j# G4 u/ t4 ~2 i* Q
5.         for (var log : logs) {
   
6.             for (int i = log[0]; i < log[1]; i++) {
     X. v* c* \" `: B% B" f) }: d
7.                 population++;
   : O9 K& \1 `  o% w$ T4 X& w
8.             }
   
9.         }
   
10.         int res = 1950;
    0 Q& s: I7 }* B& |* o: ~6 P
11.         for (int i = 1951; i <= 2050; i++) {
    
12.             if (population > population[res]) {
    
13.                 res = i;
    
14.             }
    * j, q& g$ d- r9 y  |" @) M
15.         }
    
16.         return res;
    
17.     }
    
18. }

复制代码

No.2下标对中的最大距离
& q( I" ?# F: u; e7 R9 f
解题思路
: l& k$ \4 F; D9 `' |; f
# Z( S2 a" k' f输入的两个数组都是单调的，可以使用双指针。

8 v% E  w; }/ `& d* Y. P1 F" w代码展示
( V% N% m) t- D

1. class Solution {
   
2.     public int maxDistance(int[] nums1, int[] nums2) {
   . f+ r* y6 B7 i
3.         int n = nums1.length, m = nums2.length;
   
4.         int res = 0;
   
5.         for (int i = 0, j = -1; i < n; i++) {
   1 G/ `& _- @' j+ n$ b' U
6.             while (j + 1 < m && nums1 <= nums2[j + 1]) {
   & `+ V, B* Y6 ^$ B
7.                 j++;
   
8.             }
   
9.             res = Math.max(res, j - i);
   8 N+ H, C8 B5 k
10.         }
    
11.         return res;
    1 L: @( w5 @6 R' P! a8 f0 D
12.     }
    
13. }

复制代码

No.3 子数组最小乘积的最大值
& k% Z; `+ F6 f  U# m
; e* s' `) [. H+ d; C解题思路
3 n5 A- u+ ?2 C6 a  D  [; P( o
8 r( X9 K+ V: ?3 L$ |+ V0 N单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。

3 H% v; d9 i* j- h) J) y当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。

- ?- r6 T, E  N/ R& U& N  M- i; m代码展示
, C8 k0 P$ F1 s- l9 q* z  w# c) H

1. class Solution {
   
2.     public int maxSumMinProduct(int[] nums) {
   & Z% N  _7 T! W$ P& L2 `! W- Z2 a! p
3.         int n = nums.length;
   . v7 v; A( k* O5 G0 \+ o
4.         long[] preSum = new long[n + 1];
   0 e* Z& R  Z, t, Q2 J* P
5.         for (int i = 1; i <= n; ++i) {
   
6.             preSum = preSum[i - 1] + nums[i - 1];
   
7.         }
   # ~# h5 G! i' @- z
8. 
   
9.         int[] l = new int[n];
   
10.         int[] r = new int[n];
    
11.         Arrays.fill(r, n - 1);
    7 \7 h( Q% V) l3 u& Q7 {" r
12. 
    
13.         LinkedList<Integer> stack = new LinkedList<>();
    ' l; T5 e3 o$ M' z- u
14.         for (int i = 0; i < n; i++) {
    & `6 ^! z/ F; [. e/ v& R0 ^/ y8 L
15.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    ! `) b( N2 G' L0 r4 S9 x5 A
16.                 r[stack.pollFirst()] = i - 1;
    0 i5 B' Z( c" E% L- m4 B1 |- X
17.             }
    
18.             stack.addFirst(i);
    
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;
    1 P4 N; x/ Q3 ~! R5 i; p( L
24.             }
    2 L9 |( f+ ]" S
25.             stack.addFirst(i);
    
26.         }
    7 A8 X2 |/ q) L- e
27. 
    2 L. t* D* W6 v! j
28.         long res = 0;
    # y  T2 D* H1 ?7 d
29.         for (int i = 0; i < n; i++) {
    
30.             res = Math.max(res, (preSum[r + 1] - preSum[l]) * nums);
    7 J# K7 S2 C$ q6 Z; Q
31.         }
    
32. 
    + G7 k9 d& Z  j4 T
33.         return (int) (res % 1000000007L);
    
34.     }
    
35. }

复制代码

No.4 有向图中最大颜色值
- Q. u9 e/ M1 }7 x
解题思路

先判断图中是否有环，有环直接返回 -1.

无环的话则使用动态规划求解。
; k9 F! g9 `( Z
代码展示

  V6 W/ x- M9 c1 ?

1. class Solution {
   . T- K! U/ R  R  Y+ {
2.     public int largestPathValue(String colors, int[][] edges) {
   
3.         // 建图
   
4.         int n = colors.length();
   , d: T7 `; o5 B' E
5.         Node[] nodes = new Node[n];
   
6.         for (int i = 0; i < n; i++) {
   
7.             nodes = new Node();
   9 Z2 M2 w7 ]* L/ M: l8 G9 T+ y
8.         }
   
9.         for (int[] e : edges) {
   
10.             nodes[e[0]].nei.add(nodes[e[1]]);
    , G) {. a0 a  u. i
11.         }
    
12.         // 判环
    ! a7 n2 F/ M2 T' u
13.         for (Node node : nodes) {
    * s7 t1 C7 j1 E) q
14.             if (findCircle(node)) {
    
15.                 return -1;
    
16.             }
    
17.         }
    
18.         // 动态规划
    3 Z7 E  |5 k- b2 Z# O# p
19.         int best = 0;
    % c1 J6 i+ x3 \+ Z0 \4 |# `4 a
20.         for (int i = 'a'; i <= 'z'; i++) {
    - ?' s, @0 e# C" s2 P! F( B/ C
21.             for (int j = 0; j < n; j++) {
    
22.                 nodes[j].dp = -1;
    " L# b# L4 M' u0 b- g( H7 i
23.                 nodes[j].val = colors.charAt(j) == i ? 1 : 0;
    
24.             }
    
25.             for (int j = 0; j < n; j++) {
    % ~5 d9 W% ?. ~
26.                 best = Math.max(best, dp(nodes[j]));
    
27.             }
    3 R" Y+ G2 s- [' c9 @3 J( S0 I! }
28.         }
    & w$ q/ H" P6 r9 ~
29.         return best;
    
30.     }
    ! n% h8 ^/ H$ U; R4 h- E
31. 
    . c; F% i6 K# ]* Y
32.     public int dp(Node cur) {
    4 I1 P0 E; u8 n9 d# b8 R( a
33.         if (cur.dp == -1) {
    
34.             cur.dp = 0;
    
35.             for (Node node : cur.nei) {
    4 b4 u, M6 {0 G  s
36.                 cur.dp = Math.max(cur.dp, dp(node));
    8 ~! G5 R; ?0 P  S; m2 [4 Q
37.             }
    , {' l# u: h* m; A
38.             cur.dp += cur.val;
    : D8 W. l4 }! T4 W+ K9 Y
39.         }
    
40.         return cur.dp;
    3 e/ r8 S5 I! `* U, l8 |
41.     }
    , i, }) X, d' k2 Z
42. 
    
43.     // 精简版的 Tarjan 算法：
    ' ^( ?; S1 D4 t; w& W% K, h
44.     // 仅用作判环，而无需求出强连通分量
    - i3 v; O. {: \+ f
45.     // 所以并不需要真正使用栈，只需要一个标志位即可
    * W" U. B  m4 A+ b8 k4 Q! c+ [
46.     boolean findCircle(Node cur) {
    ' K! }' Q8 j0 O: V! c
47.         if (cur.vis) {
    
48.             return cur.stk;
    
49.         }
    & v" B; a+ a& r7 a
50.         cur.vis = cur.stk = true;
    
51.         for (Node node : cur.nei) {
    
52.             if (findCircle(node)) {
    
53.                 return true;
    
54.             }
    
55.         }
    & w  X" K0 ?; g# [
56.         cur.stk = false;
    + ~( U4 K5 d6 y* Y. O5 K& [; n" x
57.         return false;
    
58.     }
    , R/ q7 G! |" ~6 d
59. }
    7 d4 b1 R5 w1 e  Q5 d* x- t" e" q
60. 
    
61. class Node {
    
62.     int val, dp;
    , q& @6 X. Z/ I# M; e- i# K& h
63.     boolean vis, stk;
    
64.     List<Node> nei;
    6 n9 o: y2 P* p5 y, J" F
65. 
    4 G4 W2 U1 s! F  Z+ s! N( ^5 y: h+ e
66.     Node() {
    + W1 z( |+ C0 ~
67.         dp = -1;
    6 O% {6 X( W: t- b
68.         nei = new ArrayList<>();
    
69.     }
    ' W+ u1 k* ?0 j4 S
70. }

复制代码