《力扣算法训练提升》数组篇-打卡数组遍历-495.提莫攻击

《力扣算法训练提升》数组篇-打卡数组遍历-495.提莫攻击

数组的基本特性

数组是最简单的数据结构。

数组是用来存储一系列相同类型数据，数据连续存储，一次性分配内存。

数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

数组索引

数组通过索引支持快速访问数据，一个长度为N的数组，它的下标从0开始到N-1结束。

数组元素可以通过数组名称加索引进行访问。元素的索引是放在方括号内，跟在数组名称的后边。

数组扩容

数组内存空间是一次性分配，扩容时，申请一块更大的内存空间，再将数据拷贝到新内存空间，时间复杂度为O(N)。

数组遍历

for (int i = 0; i < arr.length; i++) {
    // 利用arr[i]进行数组元素操作
}

力扣495. 提莫攻击

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。

你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。

具体描述

提莫攻击1 提莫攻击2

解题思路：计算下一次中毒持续时间

将全程进攻过程看做一条完整的时间段，计算下一次中毒持续时间有两种可能情况

第一种情况：相互时间段不重合

中毒开始时间  >=  上一次中毒结束时间

那么下一次中毒持续时间为完整时间段

下一次中毒持续时间 time=duration

第二种情况：部分时间段重合

中毒开始时间 < 上一次中毒结束时间

那么下一次中毒持续时间为部分不重叠时间段

下一次中毒持续时间 time=arr[i+1] - arr[i]

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组一次。

空间复杂度：O(1)

动画模拟

第一种情况：相互时间段不重合

第一种情况

第二种情况：部分时间段重合

第二种情况

示例

public static int findPoisonedDuration(int[] timeSeries, int duration) {
    if (timeSeries.length == 0) {
        return 0;
    }

    // 第一次中毒持续时间
    int durationTime = duration;
    for (int i = 0; i < timeSeries.length - 1; i++) {
        // 计算下一次中毒持续时间
        if (timeSeries[i + 1] >= timeSeries[i] + duration) {
            // 下一次中毒开始时间大于等于上一次中毒结束时间，那么下一次中毒持续时间为完整时间段
            durationTime += duration;
        } else {
            // 下一次中毒开始时间小于上一次中毒结束时间，那么下一次中毒时间需要减去公共时间段
            durationTime += timeSeries[i + 1] - timeSeries[i];
        }
    }

    return durationTime;
}

解题简化：下一次中毒持续时间

每一次考虑下一次中毒时间只有两种可能
第一种，不与上一段时间重合，自己就是完整的持续时间段，这是最大持续时间；
第二种，部分时间与上一段时间重合，需要减去重合时间段，这是较小持续时间；

第二种情况下，算得的较小持续时间一定是 小于 第一种情况的，即 duration 的
所以，取两种情况的最小值，就是下一次中毒持续时间

示例

public static int findPoisonedDuration2(int[] timeSeries, int duration) {
    if (timeSeries.length == 0) {
        return 0;
    }

    // 第一次中毒持续时间
    int durationTime = duration;
    for (int i = 0; i < timeSeries.length - 1; i++) {
        durationTime += Math.min(duration, timeSeries[i + 1] - timeSeries[i]);
    }
    return durationTime;
}

关注我了解更多精彩内容

欢迎关注：囧么肥事 (或搜索：jiongmefeishi)