大家好，又见面了，我是你们的朋友全栈君。
题目1
解法
这个题目普通解法参见这里
不过这里面的做法都是nlog(n)的。实际上利用差分数组，这道题目可以有O(n)做法
这边简单提一下差分序列，对于一个数组，差分序列的定义是数组中前一个值和后一个值的差值形成的新数组。我们在原数组某个区间加上一个统一的值，正常的做法需要在原数组每个位置去叠加，而体现在差分数组上只需要对区间两端的值进行变化即可，差分数组的prefix sum其实就是原数组。
比如原数组为：num = [1,1,1,2,2,3]
差分数组为：diff_num = [1,0,0,1,0,1], 假设num[-1] = 0
如果对原数组[0,3)的元素都+1，原数组变为：
num = [2,2,2,2,2,3],
diff_num= [1+1,0,0,1-1,0,1]
可以看到，差分数组的prefix sum与原数组一致，但差分数组只需变化两个值即可
所以差分数组常用在区间叠加的问题上
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
max_time = 0
for interval in intervals:
max_time = max(max_time,interval[0],interval[1])
diff_time = [0]*(max_time+2)
for interval in intervals:
start = interval[0]
end = interval[1]
diff_time[start] += 1
diff_time[end] -= 1
ans = 1
tmp = 0
for num in diff_time[:-1]:
tmp += num
ans = max(ans,tmp)
#print(diff_time)
return ans
题目2
解析参见这里
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/136667.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...