Easy

题目描述

设计了一个新的键盘进行测试，测试人员按顺序按下了 n 个键，每次按一个键。

给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。还给你一个长度为 n 的数组 releaseTimes ，其中 releaseTimes[i] 表示第 i 个键被释放的时间。字符串和数组的 下标都从 0 开始 。第 0 个键在时间为 0 时被按下，之后每个键都 恰好 在前一个键被释放的时刻被按下。

测试人员想要找出按键 持续时间最长 的键。第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，第 0 次按键的持续时间为 releaseTimes[0] 。

注意，测试期间，同一个键可以在不同时刻被按下多次，而每次的持续时间都可能不同。

请返回 持续时间最长 的键。如果有多个这样的键，则返回 按字典序排列最大 的那个键。

示例 1：

输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd"
输出："c"
解释：按键顺序和持续时间如下：
按键 'c' ，持续时间 9（在时刻 0 按下，在时刻 9 释放）
按键 'b' ，持续时间 29 - 9 = 20（在时刻 9 按下，在时刻 29 释放）
按键 'c' ，持续时间 49 - 29 = 20（在时刻 29 按下，在时刻 49 释放）
按键 'd' ，持续时间 50 - 49 = 1（在时刻 49 按下，在时刻 50 释放）
持续时间最长的按键是 'b' 和第二次按键 'c'，持续时间都是 20。
'c' 按字典序排列比 'b' 大，所以答案是 'c'。

示例 2：

输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
输出："a"
解释：按键顺序和持续时间如下：
按键 's' ，持续时间 12
按键 'p' ，持续时间 23 - 12 = 11
按键 'u' ，持续时间 36 - 23 = 13  
按键 'd' ，持续时间 46 - 36 = 10
按键 'a' ，持续时间 62 - 46 = 16
持续时间最长的按键是 'a' ，持续时间 16。

提示：

  • releaseTimes.length == n
  • keysPressed.length == n
  • 2 <= n <= 1000
  • 1 <= releaseTimes[i] <= 10^9
  • releaseTimes[i] < releaseTimes[i+1]
  • keysPressed 只包含小写英文字母。

解题思路

解题思路

这是一道模拟题，核心思路是遍历所有按键，计算每个按键的持续时间，找出持续时间最长的按键。

算法步骤：

  1. 计算每个按键的持续时间：

    • 第一个按键的持续时间为 releaseTimes[0]
    • 其余按键的持续时间为 releaseTimes[i] - releaseTimes[i-1]

  2. 维护最优答案：

    • 用两个变量记录当前最长持续时间和对应的按键
    • 遍历过程中更新最优解的条件：
      • 当前持续时间 > 最长持续时间，或者
      • 当前持续时间 = 最长持续时间 且 当前按键字典序更大

  3. 字典序比较：

    • 题目要求当持续时间相等时，返回字典序最大的按键
    • 直接比较字符的 ASCII 值即可

时间复杂度分析： 只需要遍历一次数组，每次操作都是 O(1)，总时间复杂度为 O(n)。

空间复杂度分析： 只使用了常数个变量存储状态，空间复杂度为 O(1)。

这种单次遍历的贪心策略是最优解法，简洁高效。

代码实现

class Solution {
public:
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        char result = keysPressed[0];
        int maxDuration = releaseTimes[0];
        
        for (int i = 1; i < releaseTimes.size(); i++) {
            int duration = releaseTimes[i] - releaseTimes[i - 1];
            if (duration > maxDuration || (duration == maxDuration && keysPressed[i] > result)) {
                maxDuration = duration;
                result = keysPressed[i];
            }
        }
        
        return result;
    }
};

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        result = keysPressed[0]
        max_duration = releaseTimes[0]
        
        for i in range(1, len(releaseTimes)):
            duration = releaseTimes[i] - releaseTimes[i - 1]
            if duration > max_duration or (duration == max_duration and keysPressed[i] > result):
                max_duration = duration
                result = keysPressed[i]
        
        return result

public class Solution {
    public char SlowestKey(int[] releaseTimes, string keysPressed) {
        char result = keysPressed[0];
        int maxDuration = releaseTimes[0];
        
        for (int i = 1; i < releaseTimes.Length; i++) {
            int duration = releaseTimes[i] - releaseTimes[i - 1];
            if (duration > maxDuration || (duration == maxDuration && keysPressed[i] > result)) {
                maxDuration = duration;
                result = keysPressed[i];
            }
        }
        
        return result;
    }
}

var slowestKey = function(releaseTimes, keysPressed) {
    let maxDuration = releaseTimes[0];
    let result = keysPressed[0];
    
    for (let i = 1; i < releaseTimes.length; i++) {
        let duration = releaseTimes[i] - releaseTimes[i - 1];
        
        if (duration > maxDuration || (duration === maxDuration && keysPressed[i] > result)) {
            maxDuration = duration;
            result = keysPressed[i];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次数组，n 为按键数量
空间复杂度O(1)只使用常数个额外变量