目标
给你一个整数数组 nums。
如果子数组中 不同偶数 的数量等于 不同奇数 的数量，则称该 子数组 是 平衡的 。
返回 最长 平衡子数组的长度。
子数组 是数组中连续且 非空 的一段元素序列。
示例 1:
输入: nums = [2,5,4,3]
输出: 4
解释:
最长平衡子数组是 [2, 5, 4, 3]。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。示例 2:
输入: nums = [3,2,2,5,4]
输出: 5
解释:
最长平衡子数组是 [3, 2, 2, 5, 4] 。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]。因此，答案是 5。示例 3:
输入: nums = [1,2,3,2]
输出: 3
解释:
最长平衡子数组是 [2, 3, 2]。
它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]。因此，答案是 3。说明:
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
提示:
- Store the first (or all) occurrences for each value in pos[val].
- Build a lazy segment tree over start indices l in [0..n-1] that supports range add and can tell if any index has value 0 (keep mn/mx).
- Use sign = +1 for odd values and sign = -1 for even values.
- Initialize by adding each value's contribution with update(p, n-1, sign) where p is its current first occurrence.
- Slide left l: pop pos[nums[l]], let next = next occurrence or n, do update(0, next-1, -sign), then query for any r >= l with value 0 and update ans = max(ans, r-l+1).
思路
// todo
代码