每日一题:LeetCode:1629.按键持续时间最长的键

浏览次数 : 次 2022-01-09

博文字数统计 : 660字 | 阅读所需时长 : 2分

× 文章目录

1. 2022-01-09：LeetCode：1629.按键持续时间最长的键
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法：数组模拟

每日一题：LeetCode：1629.按键持续时间最长的键
- 时间：2022-01-09
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：数组
- 算法：模拟

2022-01-09：LeetCode：1629.按键持续时间最长的键

1. 题目描述

题目：原题链接
- LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 n 个），每次一个。
- 给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。
- releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。
- 字符串和数组的下标都从 0 开始。第 0 个键在时间为 0 时被按下，接下来每个键都恰好在前一个键松开时被按下。
- 测试人员想要找出按键持续时间最长的键。第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，第 0 次按键的持续时间为 releaseTimes[0] 。
- 注意，测试期间，同一个键可以在不同时刻被多次按下，而每次的持续时间都可能不同。
- 请返回按键持续时间最长的键，如果有多个这样的键，则返回按字母顺序排列最大的那个键
输入输出规范
- 输入：按键数组和按键释放时间数组
- 输出：持续时间最长的按键(字符型)
输入输出示例
- 输入：releaseTimes = [9,29,49,50], keysPressed = “cbcd”
- 输出：”c”

2. 方法：数组模拟

思路：求连续的左括号的最大个数
- 本题实际上就是要求解按键数组中，哪个元素所对应的持续时间最长
- 维护两个变量，表示最大持续时间和对应的按键，可以直接遍历整个按键数组k[i]，统计每个按键对应的持续时间t[i] - t[i - 1]，并通过大小、字典序判断来更新这两个变量
- 注意求的不是累计的持续时间，而是单词的持续时间，多个答案时输出字典序最大的结果
复杂度分析：n是s字符串的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

题解：直接模拟

public char slowestKey(int[] releaseTimes, String keysPressed) {
       if (releaseTimes == null || releaseTimes.length == 0 ||
           keysPressed == null || keysPressed.length() == 0)
           return 0;
       if (releaseTimes.length != keysPressed.length()) return 0;
       int n = releaseTimes.length;
       int maxTime = releaseTimes[0];
       char maxKey = keysPressed.charAt(0);
       for (int i = 1; i < n; i++) {
           if (releaseTimes[i] - releaseTimes[i - 1] > maxTime ||
               (releaseTimes[i] - releaseTimes[i - 1] == maxTime && keysPressed.charAt(i) > maxKey)) {
               maxTime = releaseTimes[i] - releaseTimes[i - 1];
               maxKey = keysPressed.charAt(i);
           }
       }
       return maxKey;
}

本文作者： Chthollists
发布时间： 2022-01-09 14:48:56
最后更新： 2022-01-21 23:09:05
本文标题： 每日一题:LeetCode:1629.按键持续时间最长的键
本文链接： https://chthollists.github.io/post/dfb7b714.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！