LeetCode Weekly Contest 240解题报告

No.1 人口最多的年份

. j4 E5 y. J) y, h( \% G解题思路

数据范围比较小，直接枚举统计即可。
. b) j$ U2 d% b
% m+ h- x6 A8 M+ e: F5 Y9 i代码展示

1. 
   ' D) ]8 Z0 M7 M* f$ \$ ^3 L
2. class Solution {
   
3.     public int maximumPopulation(int[][] logs) {
   ; \) V; Y# T, G: r
4.         int[] population = new int[2051];
   ; O9 F$ D, B/ D( r# U5 N  u4 N
5.         for (var log : logs) {
   ; j7 C) j+ K9 G2 {! r
6.             for (int i = log[0]; i < log[1]; i++) {
   # r/ Y0 q; I, O+ V" a/ L  Q- e# q* T
7.                 population++;
   " u+ o$ f0 |/ ^$ E5 `; a
8.             }
   
9.         }
   
10.         int res = 1950;
    3 M; I! r- I" J: A: |3 {
11.         for (int i = 1951; i <= 2050; i++) {
    
12.             if (population > population[res]) {
    
13.                 res = i;
    
14.             }
    
15.         }
    
16.         return res;
    
17.     }
    
18. }

复制代码

1 ?/ K. k9 `9 o6 I! D7 |+ H
No.2下标对中的最大距离

& q, b) C+ A$ {( `/ [) e3 Z解题思路
& i: S8 D+ y) \( {0 x
2 @4 O) M5 r# U5 [! v* I. t+ L输入的两个数组都是单调的，可以使用双指针。

代码展示

1. class Solution {
   
2.     public int maxDistance(int[] nums1, int[] nums2) {
   
3.         int n = nums1.length, m = nums2.length;
   
4.         int res = 0;
   ; ]8 H' q/ J' K& _
5.         for (int i = 0, j = -1; i < n; i++) {
   
6.             while (j + 1 < m && nums1 <= nums2[j + 1]) {
   - h: p& g( c  t0 g# j% Z, w2 o
7.                 j++;
   ' }3 c8 Y) u& T  n
8.             }
   9 J  {- G, d$ M) O+ T
9.             res = Math.max(res, j - i);
   : m$ r. i4 d" R5 X# y
10.         }
    $ M2 P2 Y- ~& G
11.         return res;
    1 X" @0 ~0 \8 F7 ^+ _
12.     }
    
13. }

复制代码

+ Q4 k1 k# \1 P+ N9 N+ D/ a: CNo.3 子数组最小乘积的最大值

/ y! Q8 g) e3 i2 v) ]7 Z解题思路
: w# p1 I* E, ^- s- j. B
, Z" S* d' R# b; G$ Q1 N, b8 \5 J+ U# g单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。
6 E9 {7 T6 }0 j$ w
当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。
5 _8 |$ }8 B$ q) @  X9 i3 j3 p! G6 @
代码展示

1. class Solution {
   
2.     public int maxSumMinProduct(int[] nums) {
   
3.         int n = nums.length;
   
4.         long[] preSum = new long[n + 1];
   - R/ e6 q0 j" h
5.         for (int i = 1; i <= n; ++i) {
   , O$ m( ^6 u% y% d4 H- f3 @% ?
6.             preSum = preSum[i - 1] + nums[i - 1];
   5 L: H: w7 o0 f' ]: O+ a. _
7.         }
   1 z, t; a# l: K9 a6 p
8. 
   
9.         int[] l = new int[n];
   ) f% ]& \0 f! |. H" T( m- O) s
10.         int[] r = new int[n];
      n) _. _/ B! r
11.         Arrays.fill(r, n - 1);
    
12. 
    
13.         LinkedList<Integer> stack = new LinkedList<>();
    
14.         for (int i = 0; i < n; i++) {
    
15.             while (!stack.isEmpty() && nums[stack.peekFirst()] > nums) {
    + V5 D1 P: u& E. ~
16.                 r[stack.pollFirst()] = i - 1;
    
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) {
    . Y  c7 x! N8 H
23.                 l[stack.pollFirst()] = i + 1;
    
24.             }
    
25.             stack.addFirst(i);
    5 U) j. j' w. }) c
26.         }
    : g; a: R* [  ]1 K( F
27. 
    
28.         long res = 0;
    
29.         for (int i = 0; i < n; i++) {
    % {, j! `8 b3 N5 }3 [
30.             res = Math.max(res, (preSum[r + 1] - preSum[l]) * nums);
    ! o9 [1 `6 n: N2 |3 w9 n, R
31.         }
    
32. 
    
33.         return (int) (res % 1000000007L);
      l0 X% I! L  k# n& x% v2 v) O+ U
34.     }
    ' t$ a1 ~2 E) D6 s9 p& I
35. }

复制代码

$ @$ f( q/ q; t  C9 zNo.4 有向图中最大颜色值

解题思路
* [$ t1 |; q+ n) L( t
9 L& T8 R2 C( ~. B( U4 H先判断图中是否有环，有环直接返回 -1.
0 _+ v: E' |/ V6 v
; a2 }9 z- g: y0 x) `无环的话则使用动态规划求解。

8 U) a3 a3 G4 `代码展示

1. class Solution {
   
2.     public int largestPathValue(String colors, int[][] edges) {
   " w% c& p; f& ~# a# y) N/ i
3.         // 建图
   
4.         int n = colors.length();
   4 W5 ~" p, W  P$ T( @' y
5.         Node[] nodes = new Node[n];
   2 H, Y: S" }/ U5 l3 B/ U
6.         for (int i = 0; i < n; i++) {
   
7.             nodes = new Node();
   
8.         }
   
9.         for (int[] e : edges) {
   7 ?8 H; G1 \! y0 k
10.             nodes[e[0]].nei.add(nodes[e[1]]);
    
11.         }
    
12.         // 判环
    : w" c% y' h# \" q" f5 m) O, X0 \
13.         for (Node node : nodes) {
    
14.             if (findCircle(node)) {
    
15.                 return -1;
    
16.             }
    8 p) h) F/ W! M+ b
17.         }
    . D# a) C3 F2 s+ r1 C4 J
18.         // 动态规划
    
19.         int best = 0;
    8 i* ]: G* J& B# @
20.         for (int i = 'a'; i <= 'z'; i++) {
      a! r- N5 t, j4 U- i7 [
21.             for (int j = 0; j < n; j++) {
    
22.                 nodes[j].dp = -1;
    
23.                 nodes[j].val = colors.charAt(j) == i ? 1 : 0;
    + Y! ^. l# K5 Q9 ^, i3 ]2 V
24.             }
    
25.             for (int j = 0; j < n; j++) {
    2 @1 }5 p# u3 ]7 M* X% j6 H
26.                 best = Math.max(best, dp(nodes[j]));
    
27.             }
    & G0 Q% k6 ^! q" ?* |2 j
28.         }
    
29.         return best;
    % G7 j: p! b0 U0 W, _5 N. K
30.     }
    
31. 
    7 W) t. o& w, E% U# A
32.     public int dp(Node cur) {
      t& {5 k# ?( m8 j0 D
33.         if (cur.dp == -1) {
    & J) B, M# |+ X' Q% q8 B* P
34.             cur.dp = 0;
    " p$ c# n" V! X, N4 @
35.             for (Node node : cur.nei) {
    
36.                 cur.dp = Math.max(cur.dp, dp(node));
    
37.             }
    - _) ?8 ^+ ], x! }# G! O. n
38.             cur.dp += cur.val;
    
39.         }
    
40.         return cur.dp;
    
41.     }
    
42. 
    % Y% |3 L0 c; a- Q& _
43.     // 精简版的 Tarjan 算法：
    - a2 v" Y6 ]  m. t2 A$ S: [
44.     // 仅用作判环，而无需求出强连通分量
    
45.     // 所以并不需要真正使用栈，只需要一个标志位即可
    
46.     boolean findCircle(Node cur) {
    
47.         if (cur.vis) {
    
48.             return cur.stk;
    
49.         }
    + N. b' ^  N% ~* I
50.         cur.vis = cur.stk = true;
    
51.         for (Node node : cur.nei) {
    
52.             if (findCircle(node)) {
    
53.                 return true;
    
54.             }
      f0 R; o# E4 t2 ]  T
55.         }
    2 S8 ?/ C8 M+ T3 y8 [/ C
56.         cur.stk = false;
    - I9 E; D: [' r/ W
57.         return false;
    
58.     }
    5 k# y* P9 Z$ t6 ^! z
59. }
    " U$ ?. n% c+ m* e9 M
60. 
    3 ~( H, \; f+ z# @; }  m
61. class Node {
    3 f3 l& g) N; Q+ i/ X
62.     int val, dp;
    / B& f- t. y) [1 d6 L
63.     boolean vis, stk;
    
64.     List<Node> nei;
    
65. 
    9 j  Y( B$ g, Q( b2 `$ d5 e& g. |* L$ G: k
66.     Node() {
    2 w3 [% Z8 C" w5 D& i# I
67.         dp = -1;
    6 G- Z/ z9 Y& o4 |, L' L
68.         nei = new ArrayList<>();
    
69.     }
    
70. }

复制代码

, t6 U# r  F7 c9 V4 R- H