跳转至

3386. 按下时间最长的按钮

题目描述

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

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

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

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

 

示例 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。

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

示例 2：

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

输出： 10

解释：

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

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

 

提示：

  • 1 <= events.length <= 1000
  • events[i] == [indexi, timei]
  • 1 <= indexi, timei <= 105
  • 输入保证数组 events 按照 timei 的递增顺序排序。

解法

方法一：一次遍历

思考

按下时长为相邻事件的时间差，第一个按钮的时长即其时间戳。\(n \le 1000\)，扫一遍即可。

维护当前最长时长与对应下标；时长更大，或时长相同但下标更小，则更新。

事件已按时间排序，不必再排序。

我们定义两个变量 \(\textit{ans}\) 和 \(t\)，分别表示按下时间最长的按钮的索引和按下时间。

接下来，我们从下标 \(k = 1\) 开始遍历数组 \(\textit{events}\)，对于每个 \(k\)，我们计算当前按钮的按下时间 \(d = t2 - t1\)，其中 \(t2\) 是当前按钮的按下时间，而 \(t1\) 是前一个按钮的按下时间。如果 \(d > t\) 或者 \(d = t\) 且当前按钮的索引 \(i\) 小于 \(\textit{ans}\)，我们更新 \(\textit{ans} = i\) 和 \(t = d\)。

最后，我们返回 \(\textit{ans}\)。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{events}\) 的长度。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
8
class Solution:
    def buttonWithLongestTime(self, events: List[List[int]]) -> int:
        ans, t = events[0]
        for (_, t1), (i, t2) in pairwise(events):
            d = t2 - t1
            if d > t or (d == t and i < ans):
                ans, t = i, d
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int buttonWithLongestTime(int[][] events) {
        int ans = events[0][0], t = events[0][1];
        for (int k = 1; k < events.length; ++k) {
            int i = events[k][0], t2 = events[k][1], t1 = events[k - 1][1];
            int d = t2 - t1;
            if (d > t || (d == t && ans > i)) {
                ans = i;
                t = d;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int buttonWithLongestTime(vector<vector<int>>& events) {
        int ans = events[0][0], t = events[0][1];
        for (int k = 1; k < events.size(); ++k) {
            int i = events[k][0], t2 = events[k][1], t1 = events[k - 1][1];
            int d = t2 - t1;
            if (d > t || (d == t && ans > i)) {
                ans = i;
                t = d;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func buttonWithLongestTime(events [][]int) int {
    ans, t := events[0][0], events[0][1]
    for k, e := range events[1:] {
        i, t2, t1 := e[0], e[1], events[k][1]
        d := t2 - t1
        if d > t || (d == t && i < ans) {
            ans, t = i, d
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function buttonWithLongestTime(events: number[][]): number {
    let [ans, t] = events[0];
    for (let k = 1; k < events.length; ++k) {
        const [i, t2] = events[k];
        const d = t2 - events[k - 1][1];
        if (d > t || (d === t && i < ans)) {
            ans = i;
            t = d;
        }
    }
    return ans;
}

评论