Easy

题目描述

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

每个 events[i] = [indexi, timei] 表示在时间 timei 时按下了索引为 indexi 的按钮。

  • 数组按时间递增排序。
  • 按下按钮所需的时间是连续两次按钮按下之间的时间差。第一个按钮的时间就是它被按下的时间。

返回按下时间最长的按钮的索引。如果有多个按钮的按下时间相同且都是最长的，返回索引最小的按钮。

示例 1：

输入：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 个时间单位。

示例 2：

输入：events = [[10,5],[1,7]]
输出：10
解释：
- 索引为 10 的按钮在时间 5 被按下。
- 索引为 1 的按钮在时间 7 被按下，所以它花费了 7 - 5 = 2 个时间单位。

提示：

  • 1 <= events.length <= 1000
  • events[i] == [indexi, timei]
  • 1 <= indexi, timei <= 10^5
  • 输入保证 events 按 timei 递增排序。

解题思路

这是一道简单的数组遍历问题，核心思路是计算每个按钮事件的时间间隔，并找到最大值。

思路分析：

  1. 理解时间间隔计算：第一个按钮的时间间隔就是它的时间戳，后续按钮的时间间隔是当前时间减去前一个按钮的时间。

  2. 遍历计算：遍历所有事件，对每个事件计算时间间隔。维护当前最大时间间隔和对应的按钮索引。

  3. 处理相同时间的情况：当遇到相同的最大时间间隔时，选择索引更小的按钮。这里需要注意，我们只在时间间隔严格大于当前最大值时才更新结果。

  4. 算法步骤：

    • 初始化最大时间间隔为第一个按钮的时间戳
    • 初始化结果为第一个按钮的索引
    • 从第二个事件开始遍历，计算时间间隔
    • 如果时间间隔更大，或者时间间隔相等但索引更小，则更新结果

这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int buttonWithLongestTime(vector<vector<int>>& events) {
        int maxTime = events[0][1];
        int result = events[0][0];
        
        for (int i = 1; i < events.size(); i++) {
            int currentTime = events[i][1] - events[i-1][1];
            int currentIndex = events[i][0];
            
            if (currentTime > maxTime || 
                (currentTime == maxTime && currentIndex < result)) {
                maxTime = currentTime;
                result = currentIndex;
            }
        }
        
        return result;
    }
};

class Solution:
    def buttonWithLongestTime(self, events: List[List[int]]) -> int:
        max_time = events[0][1]
        result = events[0][0]
        
        for i in range(1, len(events)):
            current_time = events[i][1] - events[i-1][1]
            current_index = events[i][0]
            
            if (current_time > max_time or 
                (current_time == max_time and current_index < result)):
                max_time = current_time
                result = current_index
        
        return result

public class Solution {
    public int ButtonWithLongestTime(int[][] events) {
        int maxTime = events[0][1];
        int result = events[0][0];
        
        for (int i = 1; i < events.Length; i++) {
            int currentTime = events[i][1] - events[i-1][1];
            int currentIndex = events[i][0];
            
            if (currentTime > maxTime || 
                (currentTime == maxTime && currentIndex < result)) {
                maxTime = currentTime;
                result = currentIndex;
            }
        }
        
        return result;
    }
}

var buttonWithLongestTime = function(events) {
    let maxTime = events[0][1];
    let result = events[0][0];
    
    for (let i = 1; i < events.length; i++) {
        let pushTime = events[i][1] - events[i-1][1];
        if (pushTime > maxTime || (pushTime === maxTime && events[i][0] < result)) {
            maxTime = pushTime;
            result = events[i][0];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 是 events 数组的长度。算法只需要遍历一次数组，使用常数额外空间。