esc to dismiss

差分

差分算法跟 前缀和 算法刚好呼应,差分可以理解为下一个数值,减去上一个数值。在使用中需要变通。

一个典型的差分算法题是 1094. 拼车, 而在 121. 买卖股票的最佳时机 中则需要变通的使用差分。

差分的套路是先得到差分数组:如在拼车(航班也类似)中按照上下车站来增加或减少人数,然后在这个差分数组中遍历累加人数来判断是否超限。

for _, t := range trips {
    stops[start] += passengers
    stops[end] -= passengers
}

而在 买卖股票最佳时机 中,则是后一天减前一天得到每日股票价格差的差分数组,然后再对差分数组遍历累加(有条件)来得到最佳的时间段。

for i := 0; i < size; i++ {
    diffs[i] = prices[i+1] - prices[i]
}

差分算法也会和 前缀和 结合应用,比如题目 1893. 检查是否区域内所有整数都被覆盖

x