No.1 人口最多的年份

解题思路

数据范围比较小，直接枚举统计即可。

代码展示

**classSolution** {
    **publicintmaximumPopulation**(**int**[][] logs){
        **int**[] population = **newint**[2051];
        **for** (var log : logs) {
            **for** (**int** i = log[0]; i < log[1]; i++) {
                population[i]++;
            }
        }
        **int** res = 1950;
        **for** (**int** i = 1951; i <= 2050; i++) {
            **if** (population[i] > population[res]) {
                res = i;
            }
        }
        **return** res;
    }
}

No.2 下标对中的最大距离

解题思路

输入的两个数组都是单调的，可以使用双指针。

代码展示

class Solution { 
   public int maxDistance(int[] nums1, int[] nums2) { 
       int n = nums1.length, m = nums2.length; 
       int res = 0; 
       for (int i = 0, j = -1; i < n; i++) { 
           while (j + 1 < m && nums1[i] <= nums2[j + 1]) { 
               j++; 
           } 
           res = Math.max(res, j - i); 
       } 
       return res; 
   } 
} 

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

解题思路

单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。

当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。

代码展示

class Solution { 
   public int maxSumMinProduct(int[] nums) { 
       int n = nums.length; 
       long[] preSum = new long[n + 1]; 
       for (int i = 1; i <= n; ++i) { 
           preSum[i] = preSum[i - 1] + nums[i - 1]; 
       } 

       int[] l = new int[n]; 
       int[] r = new int[n]; 
       Arrays.fill(r, n - 1); 

       LinkedList<Integer> stack = new LinkedList<>(); 
       for (int i = 0; i < n; i++) { 
           while (!stack.isEmpty() && nums[stack.peekFirst()] > nums[i]) { 
               r[stack.pollFirst()] = i - 1; 
           } 
           stack.addFirst(i); 
       } 
       stack = new LinkedList<>(); 
       for (int i = n - 1; i >= 0; i--) { 
           while (!stack.isEmpty() && nums[stack.peekFirst()] > nums[i]) { 
               l[stack.pollFirst()] = i + 1; 
           } 
           stack.addFirst(i); 
       } 

       long res = 0; 
       for (int i = 0; i < n; i++) { 
           res = Math.max(res, (preSum[r[i] + 1] - preSum[l[i]]) * nums[i]); 
       } 

       return (int) (res % 1000000007L); 
   } 
}

No.4 有向图中最大颜色值 解题思路

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

无环的话则使用动态规划求解。

代码展示

class Solution { 
   public int largestPathValue(String colors, int[][] edges) { 
       // 建图 
       int n = colors.length(); 
       Node[] nodes = new Node[n]; 
       for (int i = 0; i < n; i++) { 
           nodes[i] = new Node(); 
       } 
       for (int[] e : edges) { 
           nodes[e[0]].nei.add(nodes[e[1]]); 
       } 
       // 判环 
       for (Node node : nodes) { 
           if (findCircle(node)) { 
               return -1; 
           } 
       } 
       // 动态规划 
       int best = 0; 
       for (int i = 'a'; i <= 'z'; i++) { 
           for (int j = 0; j < n; j++) { 
               nodes[j].dp = -1; 
               nodes[j].val = colors.charAt(j) == i ? 1 : 0; 
           } 
           for (int j = 0; j < n; j++) { 
               best = Math.max(best, dp(nodes[j])); 
           } 
       } 
       return best; 
   } 

   public int dp(Node cur) { 
       if (cur.dp == -1) { 
           cur.dp = 0; 
           for (Node node : cur.nei) { 
               cur.dp = Math.max(cur.dp, dp(node)); 
           } 
           cur.dp += cur.val; 
       } 
       return cur.dp; 
   } 

   // 精简版的 Tarjan 算法： 
   // 仅用作判环，而无需求出强连通分量 
   // 所以并不需要真正使用栈，只需要一个标志位即可 
   boolean findCircle(Node cur) { 
       if (cur.vis) { 
           return cur.stk; 
       } 
       cur.vis = cur.stk = true; 
       for (Node node : cur.nei) { 
           if (findCircle(node)) { 
               return true; 
           } 
       } 
       cur.stk = false; 
       return false; 
   } 
} 

class Node { 
   int val, dp; 
   boolean vis, stk; 
   List<Node> nei; 

   Node() { 
       dp = -1; 
       nei = new ArrayList<>(); 
   } 
}