Golang中使用堆进行范围加法 - 何时需要这种操作的示例？

Golang中使用堆进行范围加法 - 何时需要这种操作的示例？ 大家好，我刚刚在这个网站上发现了一个问题：https://www.programcreek.com/2014/07/leetcode-range-addition-java/

题目描述如下： “假设你有一个长度为 n 的数组，初始值全为 0，并且给定 k 个更新操作。 每个操作表示为一个三元组：[起始索引, 结束索引, 增量值]，该操作会将子数组 A[起始索引 … 结束索引]（包含起始索引和结束索引）中的每个元素增加 inc。 返回执行完所有 k 个操作后修改过的数组。”

现在，它给出了两种解决方案，一种是低效的，一种是最优的。这个低效的方法让我感到困惑：

  • 他创建了一个按开始时间排序的操作数组，以及一个按结束时间排序的最小堆
  • 然后他遍历这个数组，对于每个元素，查看堆顶，从而决定该索引处的当前答案

简单问一下：这种低效的方法在现实生活中有应用场景吗？在特定情况下，你可能被迫使用这种数组和堆的方法。我在想，如果“加法”被一个复杂的操作替换会怎样？仅仅存储到目前为止添加的总和是可行的，因为“加法”是可传递的（并且是可结合、可交换的，且只需要两个参数）。

能否请您想一个复杂的操作，它迫使你使用数组和堆的方法，仅仅是因为存储它被应用了多少次（及其参数）是不可能的或低效的？

我正在尝试构思一个场景，其中的操作迫使我们使用第一种方法。


更多关于Golang中使用堆进行范围加法 - 何时需要这种操作的示例？的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于Golang中使用堆进行范围加法 - 何时需要这种操作的示例？的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


在 Go 中，使用堆进行范围加法的高效方法通常基于差分数组，其时间复杂度为 O(n + k)。然而，你提到的低效方法（排序数组 + 最小堆）在某些特定场景下确实有应用价值，尤其是当操作本身不可简单累加或具有状态依赖时。

考虑一个复杂操作：范围最大值更新。假设每个操作不是简单的加法，而是将指定范围内的每个元素更新为 max(当前值, 增量值)。这种操作不可交换且不可简单累加，因为最终值取决于操作的应用顺序和当前状态。此时，差分数组的累加方法失效，而堆方法可以处理。

以下是 Go 中的示例实现，展示如何使用排序数组和最小堆处理范围最大值更新：

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

// 定义操作结构体
type Operation struct {
	start int
	end   int
	value int
}

// 最小堆，按结束索引排序
type MinHeap []Operation

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].end < h[j].end }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Operation))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func rangeMaxUpdate(n int, operations []Operation) []int {
	// 按起始索引排序操作数组
	sort.Slice(operations, func(i, j int) bool {
		return operations[i].start < operations[j].start
	})

	result := make([]int, n)
	opIndex := 0
	h := &MinHeap{}
	heap.Init(h)

	// 遍历每个数组索引
	for i := 0; i < n; i++ {
		// 将起始索引等于当前索引的操作加入堆
		for opIndex < len(operations) && operations[opIndex].start == i {
			heap.Push(h, operations[opIndex])
			opIndex++
		}

		// 移除已结束的操作（结束索引小于当前索引）
		for h.Len() > 0 && (*h)[0].end < i {
			heap.Pop(h)
		}

		// 应用当前有效的操作中的最大值
		currentMax := 0
		if h.Len() > 0 {
			// 遍历堆中所有有效操作，找出最大值
			for _, op := range *h {
				if op.value > currentMax {
					currentMax = op.value
				}
			}
		}
		result[i] = currentMax
	}

	return result
}

func main() {
	n := 5
	operations := []Operation{
		{0, 2, 3},
		{1, 3, 5},
		{2, 4, 2},
	}

	result := rangeMaxUpdate(n, operations)
	fmt.Println(result) // 输出: [3 5 5 5 2]
}

在这个例子中，每个操作将指定范围内的元素更新为给定值（如果该值大于当前值）。由于操作不可累加，必须跟踪所有覆盖当前索引的操作，并从中选择最大值。堆用于高效移除已结束的操作，而排序数组确保按顺序处理起始索引。

另一个场景是范围乘法更新，其中每个操作将指定范围内的元素乘以一个因子。如果因子可能为零或负数，操作的顺序会影响最终结果，此时也需要跟踪所有覆盖当前索引的操作。

// 示例：范围乘法更新（简化版，仅展示操作结构）
type MultOperation struct {
	start int
	end   int
	factor float64
}
// 处理逻辑类似，但需要维护当前累积的乘积而非最大值

这些例子表明，当操作具有非交换性、状态依赖性或不满足累加性质时，堆方法成为必要选择。

回到顶部