每日leetcode第0006天 0495. Teemo Attacking

这道题目直觉可以使用布尔类型标记数组来做,时间复杂度就会是n×duration,空间复杂度也会变大到n。

于是使用了一个数学思路。

就是如果上一次的时间减去这一次的时间大于持续时间,那么就说明上一次的持续时间是满的。

如果上一次的时间减去这一次的时间小于持续时间,那么就说明上一次的持续时间有部分是浪费的,只持续了两次时间的差。

这样时间复杂度就会下降到n,空间复杂度就会下降到1。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。