Leetcode 差分数组的应用「建议收藏」

全栈程序员站长

发布于 2022-09-05 15:15:38

3690

发布于 2022-09-05 15:15:38

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

题目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