[leetcode/lintcode 题解] 算法面试高频题详解：亮起时间最长的

描述
有一排 26 个彩灯，编号从 0 到 25，现在给出了一系列控制指令来控制这些彩灯的开关。
一开始这些彩灯都是关闭的，然后指令将逐条发出。
在每条指令operation[i]中含有两个整数 operationi, operationi。
在接收到一条指令时，标号为 operationi 的彩灯会亮起，直到第 operationi 秒的时候熄灭。
当灯熄灭后，下一条指令将会发出。
其中第一条指令将在第0秒的时候发出，并被立刻执行。
你的任务是找到哪个彩灯单次亮起的时间最长。

1≤n≤1051≤n≤105
0≤keyTimesi≤25(0≤i n)0≤keyTimesi≤25(0≤i n)
0≤keyTimesi≤108(0≤i n)0≤keyTimesi≤108(0≤i n)
保证至少有一个按键.
保证 keyTimes 是按照 keyTimesi 升序排序的.

在线评测地址：领扣题库官网

样例1
[[0,2],[1,5],[0,9],[2,15]]
operation = `[[0, 2], [1, 5], [0, 9], [2, 15]]`
在第0秒的时候，接收到指令`[0, 2]`，此时标号为 0 的灯亮起，第 2 秒的时候熄灭。此时 0号灯 的单次亮起时间为`2-0 = 2` 秒。
在第2秒的时候，接收到指令`[1, 5]`，此时标号为 1 的灯亮起，第 5 秒的时候熄灭。此时 1号灯 的单次亮起时间为 `5-2 = 3` 秒。
在第5秒的时候，接收到指令`[0, 9]`，此时标号为 0 的灯亮起，第 9 秒的时候熄灭。此时 0号灯 的单次亮起时间为 `9-5 = 4` 秒。
在第9秒的时候，接收到指令`[2, 15]`，此时标号为 2 的灯亮起，第 15 秒的时候熄灭。此时 2号灯 的单次亮起时间为 `15-9 = 6` 秒。
所以单次亮起的最长时间为 `max(2, 3, 4, 6) = 6` 秒，是标号为 `2` 的彩灯。
**你需要返回一个小写英文字母代表这个编号。`如 'a' 代表 0，'b' 代表 1，'c' 代表 2 ... 'z' 代表 25。`**
所以你的答案应该是`'c'`

算法：模拟
解题思路：
模拟路灯开关的过程，并记录最长的灯亮的时间，以及当前亮起时间最长的灯。
复杂度分析：
时间复杂度：O(n)
n为数组的长度。
空间复杂度：O（1）
代码：

public class Solution {
 * @param operation: A list of operations.
 * @return: The lamp has the longest liighting time.
 public char longestLightingTime(List List Integer operation) {
 int maxTime = operation.get(0).get(1);
 char answer = (char)('a' + operation.get(0).get(0));
 int n = operation.size();
 for (int i = 0; i n - 1; i++) {
 List Integer next = operation.get(i + 1);
 List Integer current = operation.get(i);
 int time = next.get(1) - current.get(1);
 if (time maxTime) {
 maxTime = time;
 answer = (char)(next.get(0) + 'a');
 return answer;
}

更多题解参考：九章官网solution
https://www.jiuzhang.com/solution/longest-lighting-time/?utm_source=sc-tianchi-sz-0406

本文转自网络，原文链接：https://developer.aliyun.com/article/783347
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！