leetcode
leetcode 2801 ~ 2850
生存人数

生存人数

难度:

标签:

题目描述

Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive. You may assume that all people were born between 1900 and 2000 (inclusive). If a person was alive during any portion of that year, they should be included in that year's count. For example, Person (birth= 1908, death= 1909) is included in the counts for both 1908 and 1909.

If there are more than one years that have the most number of people alive, return the smallest one.

 

Example: 

Input: 
birth = [1900, 1901, 1950]
death = [1948, 1951, 2000]
Output:  1901

 

Note:

  • 0 < birth.length == death.length <= 10000
  • birth[i] <= death[i]

代码结果

运行时间: 35 ms, 内存: 16.9 MB

/*
 * 题目思路：
 * 1. 使用两个Map记录每一年的人数变化。
 * 2. 遍历所有出生年份和死亡年份，更新Map中的人数变化。
 * 3. 将所有年份按顺序遍历，通过Stream计算每一年的生存人数。
 * 4. 找出生存人数最多的年份，如果有多个年份生存人数相同，返回最小的年份。
 */

import java.util.*;
import java.util.stream.*;

public class MaxAliveYearStream {
    public int maxAliveYear(int[] birth, int[] death) {
        Map<Integer, Integer> yearCounts = new HashMap<>();
        for (int i = 0; i < birth.length; i++) {
            yearCounts.put(birth[i], yearCounts.getOrDefault(birth[i], 0) + 1);
            yearCounts.put(death[i] + 1, yearCounts.getOrDefault(death[i] + 1, 0) - 1);
        }

        int[] maxAliveYear = {1900};
        int[] maxAlive = {0};
        int[] currentAlive = {0};

        yearCounts.keySet().stream().sorted().forEach(year -> {
            currentAlive[0] += yearCounts.get(year);
            if (currentAlive[0] > maxAlive[0]) {
                maxAlive[0] = currentAlive[0];
                maxAliveYear[0] = year;
            }
        });

        return maxAliveYear[0];
    }

    public static void main(String[] args) {
        MaxAliveYearStream solution = new MaxAliveYearStream();
        int[] birth = {1900, 1901, 1950};
        int[] death = {1948, 1951, 2000};
        System.out.println(solution.maxAliveYear(birth, death)); // 输出: 1901
    }
}

解释

方法:

该题解使用了一种称为'差分数组'的技巧来计算每一年的生存人数。首先，定义一个差分数组`diff`，其中`diff[i]`表示第`i`年相比于前一年生存人数的变化量。遍历每个人，将他们的出生年份在差分数组中增加1（表示从这一年开始，人数增加了一个），而在他们死亡年份的次年减少1（表示从这一年开始，人数减少了一个）。遍历完成后，通过累加差分数组来得到每一年的具体生存人数。在此过程中，寻找并记录生存人数最多的年份。如果多个年份的人数相同，则由于数组是按年份顺序处理的，会自然选择最小的年份。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到的差分数组技术是如何准确处理人群在死亡后次年人数减少的？
▷
在差分数组中，对于每一个人的出生年份`b`，数组在`b - minVal`的位置上加1，表示从这一年开始生存人数增加。而在死亡年份`d`的次年，也就是`d-minVal+1`位置上减1，这代表从这一年开始人数减少，因为这个人不再算在生存人数中。这种方法可以确保在人死亡的那一年他/她仍然被计入生存人数，而从下一年开始不再被计算。
🦆
在初始化差分数组时，为什么数组的长度是`maxVal - minVal + 2`而不是`maxVal - minVal + 1`？
▷
数组长度为`maxVal - minVal + 2`是为了确保在差分数组中能够处理最大死亡年份`maxVal`的次年的人数变化。如果数组长度只有`maxVal - minVal + 1`，那么对于最大的死亡年份`maxVal`来说，其次年`maxVal - minVal + 1`的索引将超出数组的范围，造成数组越界错误。通过将数组长度设为`maxVal - minVal + 2`，可以安全地在`maxVal - minVal + 1`位置上操作，从而准确地处理所有年份的人数变化。
🦆
为什么在累加差分数组计算每年的实际人数时从索引1开始遍历而不是从0开始？
▷
累加差分数组以计算实际人数时从索引1开始是因为索引0的位置已经是累加的结果，代表最小出生年份`minVal`的生存人数，即初始的人数变化。从索引1开始累加是为了更新差分数组，将每一年与前一年的人数变化累加，以此得到每一年的实际生存人数。如果从索引0开始，则会重复计算第一年的人数，导致错误的统计结果。

相关问题

最大数值跳水板