⭐ 题目日期：

字节 - 2024/11/11

🌳 题目描述：

输入二维数组，第一列是用户 id，第二列是登录时间，第三列是退出时间，统计用户最大峰值和对应时间段。

🕵🏽 面试评估：

这道题主要考查将常见的业务场景转化成算法模型的思维能力，综合难度中等偏上。

🧗 难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

登录，用户数 + 1；退出，用户数 - 1； 所以用户的行为数据（登录和退出）可以简化为 1，-1 的数组，而数组的索引为登录和退出的具体时间。举例：

1 1 1 -1 -1 1 -1 -1

最大的峰值为最大子数组的和

起始时间段：连续和的最大高度最上面的 1 对应的时间 1 1 1 -1 -1 1 -1 -1

结束时间段：连续和的最大高度最上面的 1 之后的 -1；1 1 1 -1 -1 1 -1 -1

最大峰值：1 1 1 -1 -1 1 -1 -1 = 3

💻代码：

Java

public class PeakInterval {

    // 定义事件类，type: 1 表示进入事件，-1 表示退出事件
    private class Event {
        int time;
        int type;

        Event(int time, int type) {
            this.time = time;
            this.type = type;
        }
    }

    private class Result {
        int maxUsers;
        int peakStart;
        int peakEnd;

        Result(int maxUsers, int peakStart, int peakEnd) {
            this.maxUsers = maxUsers;
            this.peakStart = peakStart;
            this.peakEnd = peakEnd;
        }
    }

    public Result findPeakInterval(int[][] logs) {
        List<Event> events = new ArrayList<>();

        // 将每个用户的登录和登出时间转化为进入和退出事件
        for (int[] log : logs) {
            int loginTime = log[1];
            int logoutTime = log[2];
            events.add(new Event(loginTime, 1));
            events.add(new Event(logoutTime, -1));
        }

        // 按时间排序，时间相同则退出事件在前
        Collections.sort(events, (a, b) -> a.time == b.time ? a.type - b.type : a.time - b.time);

        int currentUsers = 0;
        int maxUsers = 0;
        int peakStart = -1;
        int peakEnd = -1;

        for (int i = 0; i < events.size(); i++) {
            Event event = events.get(i);
            currentUsers += event.type;
            if (currentUsers > maxUsers) {
                maxUsers = currentUsers;
                peakStart = event.time;
                if (i < events.size() - 1 && events.get(i + 1).type == -1) {
                    peakEnd = events.get(i + 1).time;
                }
            }
        }

        return new Result(maxUsers, peakStart, peakEnd);
    }

🚵🏻复杂度分析：

假设 n 为用户数

时间复杂度: O(nlogn)，登录数据加上退出数据一共 2n, 对所有数据进行排序, 时间复杂度为 O(2nlog2n) ~ O(nlogn)

空间复杂度: O(n), 存储所有事件，一共 2n, 空间复杂度为 O(2n) ~ O(n)