Leetcode 3721. 最长平衡子数组 II（最大后缀和，最小后缀和线段树）

题目大意

给你一个整数数组 nums。

如果子数组中 不同偶数 的数量等于 不同奇数 的数量，则称该 子数组 是 平衡的 。

返回 最长 平衡子数组的长度。

子数组 是数组中连续且 非空 的一段元素序列。

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^5

思路讲解

https://leetcode.cn/problems/longest-balanced-substring-ii/description/?envType=daily-question&envId=2026-02-13

其实这种平衡子串类似的问题，都是枚举右维护左。就是我们先确定了结尾，然后要去比较快速的找到开头，那么像这道，上面这道题目也是一样的。

这道题目维护左是采用的是线段数二分，使用线段数二分，在知道右边的情况下去找到左边。这该线段树需要维护区间，其实就是该线段树需要维护最大子段和和最小子段和。该线段树需要能够支持查询区间最大子段和和最小子段和。

不过我们仔细细想以后发现，应该这道题目维护的是最大后缀和和最小后缀和。实际上我们使用小白逛公园的线段树也可以维护最大后缀和和最小后缀和。

为什么要维护最大子段和和最小子段和呢？它实际上是这样子，它首先是把奇数变成一，偶数变成负一。当然都是最右边的那个值啊，奇数变成一，偶数变成负一。然后如果说我们知道了这一段的最大子段和是多少，最小子段和是多少，那么其实这一段的子段和是否有零？

显然，暴力解法无法满足时间要求，我们需要找到一个时间复杂度较低的方法来快速找到最长平衡子数组，于是我想到了线段树，通过区间修改和快速查询，可以实现时间复杂度O(N log N)。

那么如何用线段树快速找到最长平衡子数组呢，我们可以规定，如果数字是 偶数+1，反之，如果是 奇数-1。那这个问题就转换为，我们要找到 区间和 为0 的最长子区间长度。

但题目还有一个数字去重的要求，如果数字相同，则不能重复计算贡献，那我们可以这么想：

换句话说，我更新区间和的时候，只从 j 点更新到上一次这个数字出现前的位置（也就是图中1的位置），再往后这个数字就不能贡献计数了。

好了，线段树构造好了，那如何快速找到 区间和 为 0 的 子区间呢？由于这个线段树没有单调性，如果用朴素的方法，我们可能需要遍历整棵树，复杂度来到了O(N)，不符合要求，解决方法是，采取Min/Max 剪枝策略，具体如下：在每个节点除了记录区间和，还要记录区间最大和 Max 和区间最小和 Min，并在寻找 区间和为 0 的时候做以下判断：

这样，就像走迷宫有了导航，复杂度可以下降到 O(Log N) :

以下为具体线段树更新和查找步骤图示：

回顾一下线段树算法的核心流程：

AC代码

源代码

// 线段树节点
type Node struct {
	Min int // 区间内的最小值
	Max int // 区间内的最大值
}

// 全局变量，避免传参过多
var (
	tree []Node
	lazy []int
	n    int
)

// 初始化线段树
func build(node, start, end int) {
	if start == end {
		tree[node] = Node{0, 0}
		return
	}
	mid := (start + end) / 2
	build(2*node, start, mid)
	build(2*node+1, mid+1, end)
	tree[node] = Node{0, 0} // 初始全为0
}

// 下推懒标记
func pushDown(node int) {
	if lazy[node] != 0 {
		lazy[2*node] += lazy[node]
		tree[2*node].Min += lazy[node]
		tree[2*node].Max += lazy[node]

		lazy[2*node+1] += lazy[node]
		tree[2*node+1].Min += lazy[node]
		tree[2*node+1].Max += lazy[node]

		lazy[node] = 0
	}
}

// 区间更新
func update(node, start, end, l, r, val int) {
	if l > end || r < start {
		return
	}
	if l <= start && end <= r {
		tree[node].Min += val
		tree[node].Max += val
		lazy[node] += val
		return
	}
	pushDown(node)
	mid := (start + end) / 2
	update(2*node, start, mid, l, r, val)
	update(2*node+1, mid+1, end, l, r, val)
	
	// 更新当前节点的最值
	tree[node].Min = min(tree[2*node].Min, tree[2*node+1].Min)
	tree[node].Max = max(tree[2*node].Max, tree[2*node+1].Max)
}

// 带有范围限制的查询
func queryRangeZero(node, start, end, L, R int) int {
	// 区间无交集
	if start > R || end < L {
		return -1
	}
	// 剪枝
	if tree[node].Min > 0 || tree[node].Max < 0 {
		return -1
	}
	if start == end {
		if tree[node].Min == 0 {
			return start
		}
		return -1
	}
	
	pushDown(node)
	mid := (start + end) / 2
	
	res := queryRangeZero(2*node, start, mid, L, R)
	if res != -1 {
		return res
	}
	return queryRangeZero(2*node+1, mid+1, end, L, R)
}

func longestBalanced(nums []int) int {
    n = len(nums)
	if n == 0 {
		return 0
	}

	// 初始化线段树大小 (4 * n)
	tree = make([]Node, 4*n)
	lazy = make([]int, 4*n)
	build(1, 0, n-1)

	lastPos := make(map[int]int) // 记录元素上一次出现的位置
	maxLen := 0

	for i := 0; i < n; i++ {
		val := nums[i]
		
		// 获取该元素上一次出现的位置，如果没有则视为 -1
		prev, exists := lastPos[val]
		if !exists {
			prev = -1
		}
		
		// 确定更新方向：偶数+1，奇数-1
		diff := 0
		if val%2 == 0 {
			diff = 1
		} else {
			diff = -1
		}
		
		// 核心逻辑：只更新 (上一次出现位置, 当前位置] 这个范围
		// 这意味着对于在这个范围内的起始点 start，nums[i] 是一个新的 distinct 元素
		update(1, 0, n-1, prev+1, i, diff)
		
		// 记录位置
		lastPos[val] = i
		
		firstZeroIndex := queryRangeZero(1, 0, n-1, 0, i)
		if firstZeroIndex != -1 {
			currentLen := i - firstZeroIndex + 1
			if currentLen > maxLen {
				maxLen = currentLen
			}
		}
	}

	return maxLen
}

心路历程（WA，TLE，MLE……）