Nuggets team number online, help you Offer impromptu! Click for details

preface

Most of you have played league of Legends, a MOBA game. As a coder, in addition to studying every day, I should also have some time for entertainment, such as playing games and watching movies with my friends. Proper relaxation can help improve the efficiency of study. Let’s finish this and go to summoner canyon.

Topic describes

In the League of Legends world, there is a hero named Timo whose attacks can poison the enemy hero Ash. Now, to give the time sequence of Timo’s attack on Ash and the duration of Timo’s attack, you need to output the total length of time Ash was poisoned.

You could argue that Timo attacked at a given point in time and immediately poisoned Ash.

Example 1:

Input: [1,4], 2 Output: 4 Cause: At the beginning of the first second, Timo begins to attack Ash and immediately poisons her. The poison lasts for 2 seconds until the end of the second. At the beginning of the fourth second, Timo attacked Ash again, giving Ash another two seconds to poison. So the final output is 4 seconds.Copy the code

Example 2:

Input: [1,2], 2 Output: 3 Cause: At the beginning of the first second, Timo begins to attack Ash and immediately poisons her. The poison lasts for 2 seconds until the end of the second. But at the beginning of the second, Timo again attacked Ash, who was already in a poisoned state. Timo's attack at the beginning of second will now end at the end of third second as poison does not stack. So the final output is 3.Copy the code

Tip:

  1. You can assume that the total length of the time series array is no more than 10,000.
  2. You can assume that both the numbers in the Timo attack time series and the poison duration of the Timo attack are non-negative integers and do not exceed 10,000,000.

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

In this case we can define a variable end to maintain the time boundary of each poisoning, as we traverse to the ith coordinate. If end is less than or equal to num[I], the poisoning has ended before num[I] seconds /, and the poisoning duration is duration. As shown in the figure, when it comes to the fourth second, since the end value is 4, the poisoning time in the middle is 3 seconds

Num [I]-num[i-1] = num[I] = num[I -1] = num[I -1] = num[I -1] When it reaches the fifth second, since the end value is 7, it is greater than 5, so the intermediate poisoning time is 5-4 = 1.

The final code

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int totalDuration = 0;
        int end = 0;
        for (int i = 0; i < timeSeries.length; i++) {
            if (end <= timeSeries[i]) {
                totalDuration += duration;
            } else {
                totalDuration += timeSeries[i] - timeSeries[i - 1];
            }
            end = timeSeries[i] + duration;// Recalculate the poisoning boundary
        }
        returntotalDuration; }}Copy the code

conclusion

In this case, only a single scan of the timeSeries is required. The time complexity is O(n). Note only the size of each duration and the two adjacent elements of the array. Because there is no poisoning when the array length is 0, and the last poisoning time must be duration. By default, the last poisoning time is counted as the 0th time, the 0th time is added to the duration, and then the time difference between adjacent elements is taken.

This article is participating in “Digging gold in April 2021 swipe card”, click to see the activity details. Give it a thumbs up if you like.