Leetcode周赛 240（上）

大家好，这里是一起打 Leetcode 竞赛系列文章的第 3 篇。

本周是 Leetcode周赛 240，本文会包括每一题的简单讲解，代码，难度分析，以及一些个人对这题的看法等，希望大家喜欢！

注意 ：题解并不一定都是最优解（代码以pass 了 LeetCode 的 Oline Judge 为准），文章初衷是给读者们提供一定的想法和问题的解决方案。

前言 : 参加Contest 的好处

1. 每周抽点时间去练习和学习新的题目这对于个人的编程能力与问题解决能力都有很大的帮助
2. 在规定的时间内解决一定的题目，这和真实的OA (Online Assessment) 或者 Onsite 面试是一样的，可以把它当作一个很好的 Mock 练习机会
3. 当你有碰到做不出的题目的时候，你能知道自己的弱项在哪里，然后可以根据这进行加强和练习，比赛是一面给自己的镜子

对本场比赛的一些看法

本场比赛二三四题都是很不错的题。

三四题稍微有点难度需要进行一定的思考。

今天的每道题都是多解题，本文只提供比赛时的代码和想法，建议大家可以去再多多思考一下。

1854. 一道简单的暴力签到题，会编程的人基本都要会的入门题目

1855. 因为给的数组都是排好序的，第一想法是二分法，当然这题也可以使用双指针

1856. 一道使用单调栈解决的题目，与LC84相似

1857. 此题考核了两个考点，一是有向图找环，二是拓展排序

1854 Maximum Population Year

题意：

给你一个二维数组，A[i] = [birth, death] 表示这个人活在 [birth : death-1] 这区间里，问哪一年人口最多？如果有多个最多人口的那一年，返回最早那个

logs = [[1950,1961],[1960,1971],[1970,1981]] 1960 和1970都有两个人，1960是更早的那一年

思路：

1. 因为数据不大的关系，比起用hashMap，我们可以直接用一个count 数组去记录每一年的人口然后找到最人数最多且早的那个就行了。
   
   
2. 更优的方法可以使用线扫描去记录人口，可以参考LC 1109 线扫描的具体使用方法

代码1：

class Solution {
    public int maximumPopulation(int[][] logs) {
        int cnt[] = new int[2051];
        int mx = 0;
        for (int p[]: logs) {
            for (int j = p[0]; j < p[1]; j++) {
                cnt[j]++;//记录每一年的人口
                mx = Math.max(mx, cnt[j]);//update 最多的人口是多少
            }
        }
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] == mx) return i;//返回人口最多且最早的那一年
        }
        return -1;
    }
}

空间复杂度和时间复杂度：

• 时间复杂度：O(n*m)
• 空间复杂度：O(m)
• n 是logs 数组的长度，m是这里开的是2050
  
  

代码2：

这里使用了线扫描，时间复杂度降到了 max(n,m)，详细的线扫描用法可以参考LC 1109

class Solution {
    public int maximumPopulation(int[][] logs) {
        int line[] = new int[2052];
        int cnt[] = new int[2052];
        int mx = 0;
        for (int p[]: logs) {
            line[p[0]]++;
            line[p[1]]--;
        }
        int sum = 0;
        for (int i = 0; i < line.length; i++) {//使用线扫描去记录每一年的人口
            sum += line[i];
            cnt[i] = sum;
            mx = Math.max(mx, sum);
        }
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] == mx) return i;//返回人口最多且最早的那一年
        }
        return -1;
    }
}

空间复杂度和时间复杂度：

• 时间复杂度：max(n,m)
• 空间复杂度：O(m)
• n 是logs 数组的长度，m是这里开的是2050
  
  

1855 Maximum Distance Between a Pair of Values

题意：

给你两个降序的数组，对于数A[i]，我们要在数组B中找到一个数B[j]，并且要符合 i <= j 和 A[i] <=B[j]，此时他们的距离是 j - i, 求最大的距离是多少？

nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5] 这里有效的对有(0,0), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)，而最大的距离发生在 (2，4)

思路：

1. 因为数组都是排好序的，第一个想法是使用二分法
   
   
2. 我们可以枚举每一个数组A的数字，对于每个数字，我们只要用二分法找到数组B中index最大并且这个数还比A还大的数即可。如果当前是A[i]，我们要在 [i: B.length-1] 这区间里进行搜索
   
   
3. 如果mid 比大于或等于A[i]的话我们可以更新一下答案同时把左指针往右移动，否则的话把右指针往左移动
   
   

代码1：

class Solution {
    public int maxDistance(int[] A, int[] B) {
        int res = 0;
        for (int i = 0; i < A.length; i++) {//枚举A
            int l = i, r = B.length - 1;//因为j>=i 的缘故，在区间[i,B.length-1]进行搜索
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (B[mid] >= A[i]) {//条件符合，记录一下，然后把左指针向右shift
                    res = Math.max(res, mid - i);
                    l = mid + 1;
                } else {//条件不符合，移动右指针
                    r = mid - 1;
                }
            }
        }
        return res;
    }
}

空间复杂度和时间复杂度：

• 时间复杂度：O(n log(m))
• 空间复杂度：O(1)
• n 是数组A的长度，m是数组B的长度