题目描述

给你一个二维数组 events，表示孩子在键盘上按下一系列按钮触发的按钮事件。

每个 events[i] = [index_i, time_i] 表示在时间 time_i 时，按下了下标为 index_i 的按钮。

• 数组按照 time 的递增顺序排序。
• 按下一个按钮所需的时间是连续两次按钮按下的时间差。按下第一个按钮所需的时间就是其时间戳。

返回按下时间 最长 的按钮的 index。如果有多个按钮的按下时间相同，则返回 index 最小的按钮。

样例

输入： events = [[1,2],[2,5],[3,9],[1,15]]

输出： 1

解释：

下标为 1 的按钮在时间 2 被按下。
下标为 2 的按钮在时间 5 被按下，因此按下时间为 5 - 2 = 3。
下标为 3 的按钮在时间 9 被按下，因此按下时间为 9 - 5 = 4。
下标为 1 的按钮再次在时间 15 被按下，因此按下时间为 15 - 9 = 6。

最终，下标为 1 的按钮按下时间最长，为 6。

输入： events = [[10,5],[1,7]]

输出： 10

解释：

下标为 10 的按钮在时间 5 被按下。
下标为 1 的按钮在时间 7 被按下，因此按下时间为 7 - 5 = 2。

最终，下标为 10 的按钮按下时间最长，为 5。

限制

• 1 <= events.length <= 1000
• events[i] == [index_i, time_i]
• 1 <= index_i, time_i <= 10^5
• 输入保证数组 events 按照 time_i 的递增顺序排序。

算法

(模拟) $O(n)$

1. 遍历数组，按照题目描述更新最大时间。

时间复杂度

• 遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int buttonWithLongestTime(vector<vector<int>>& events) {
        const int n = events.size();
        int ans = events[0][0], ma = events[0][1];

        for (int i = 1; i < n; i++)
            if (ma < events[i][1] - events[i - 1][1]) {
                ma = events[i][1] - events[i - 1][1];
                ans = events[i][0];
            } else if (ma == events[i][1] - events[i - 1][1]) {
                ans = min(ans, events[i][0]);
            }

        return ans;
    }
};