[leetcode 3479][线段树]水果成蓝 III

inkOrCloud2025-10-302025-10-30

题目链接

leetcode 3479 水果成蓝 III

前置概念

线段树

主要用于区间查找和区间更新，本质是一种完美二叉树，尤其适用于区间统计操作，例如区间求和，区间最值，区间最大公约数等

线段树将一个数组递归划分为若干个子数组，每个节点代表一个区间，节点值即为该区间的统计数据(最值、求和、最大公约数)，所以叶子即对应每个元素

结构特点

节点数量:对于n个元素的数组，节点数量通常不超过4n 时间复杂度: - 建树: - 单点/区间更新(区间更新配合懒标记): - 区间查询:

建树(区间最大值)

var n = len(arr)
var tree = make([]int, 4*n)
var build func(int, int, int)
   //i代表当前节点在tree中的对应下标，l/r表示i锁代表arr区间的左右边界
build = func(i int, l int, r int) {
       //当l == r时说明当前节点是叶子节点(区间长度为1)
	if l == r {
		tree[i] = arr[l]
		return
	}
	leftChild, rightChild := i*2+1, i*2+2
	m := (l + r) / 2
	build(leftChild, l, m)
	build(rightChild, m+1, r)
	tree[i] = max(tree[leftChild], tree[rightChild])
}
build(0, 0, n-1)

区间查询

//ql/qr表示需要查找的区间
var query = func(i, l, r, ql, qr int) {
    if qr < l || r < ql {
        return math.MinInt32
    }
    if ql <= l && qr >= r {
        return tree[i]
    }
    m := (l+r)/2
    leftChild, rightChild := i*2+1, i*2+2
    left := query(leftChild, l, m)
    right := query(rightChild, m+1, r)
    return max(left, right)
}

解题思路

建立一个线段树tree，用于统计baskets每个区间的最大值，再遍历fruits数组，找出大于fruits[i]的最靠左的baskets[j]，并将baskets[j]更新为-1

func numOfUnplacedFruits(fruits []int, baskets []int) int {
	var n = len(fruits)
	var tree = make([]int, 4*n)
	var build func(int, int, int)
	build = func(i int, l int, r int) {
		if l == r {
			tree[i] = baskets[l]
			return
		}
		leftChild, rightChild := i*2+1, i*2+2
		m := (l + r) / 2
		build(leftChild, l, m)
		build(rightChild, m+1, r)
		tree[i] = max(tree[leftChild], tree[rightChild])
	}
	build(0, 0, n-1)
	var ret = 0
	for _, v := range fruits {
		i := 0
		for {
            //因为所有有效节点必定大于0，所以可以通过子节点是否大于0来判断当前节点是否为叶子节点
			if i*2+2 < 4*n && tree[i*2+1] != 0 && tree[i*2+2] != 0 {
				if v > tree[i*2+1] {
					i = i*2 + 2
				} else {
					i = i*2 + 1
				}
			} else {
				break
			}
		}
		if tree[i] >= v {
            //将使用后的节点更新为-1
			tree[i] = -1
			i = (i - 1) / 2
			for ; i > 0; i = (i - 1) / 2 {
                //向上逐层更新
				tree[i] = max(tree[i*2+1], tree[i*2+2])
			}
		} else {
			ret++
		}
	}
	return ret
}