标签： todo

目标

特殊的二进制字符串 是具有以下两个性质的二进制序列：

• 0 的数量与 1 的数量相等。
• 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制字符串 s。

一次移动操作包括选择字符串 s 中的两个连续的、非空的、特殊子串，并交换它们。两个字符串是连续的，如果第一个字符串的最后一个字符与第二个字符串的第一个字符的索引相差正好为 1。

返回在字符串上应用任意次操作后可能得到的字典序最大的字符串。

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在 s[1] 出现） 和 "1100" （在 s[3] 出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

示例 2：

输入：s = "10"
输出："10"

说明：

• 1 <= s.length <= 50
• s[i] 为 '0' 或 '1'。
• s 是一个特殊的二进制字符串。

思路

代码

性能

目标

给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s。

如果一个 子串 中所有 不同 字符出现的次数都 相同，则称该子串为 平衡 子串。

请返回 s 的 最长平衡子串 的 长度 。

子串 是字符串中连续的、非空 的字符序列。

示例 1：

输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。

示例 2：

输入： s = "aabcc"
输出： 3
解释：
最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 1 次。

示例 3：

输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。

说明：

• 1 <= s.length <= 10^5
• s 仅包含字符 'a'、'b' 和 'c'。

思路

定义平衡子串是字符出现次数相同的字符串，给定一个由 a b c 三种字符组成的字符串，返回最长的平衡子串长度。

// todo

代码

性能

目标

给你一个整数数组 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

代码

性能

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。

一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。

你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。

请你返回这些子数组的 最小 总代价。

示例 1：

输入：nums = [1,3,2,6,4,2], k = 3, dist = 3
输出：5
解释：将数组分割成 3 个子数组的最优方案是：[1,3] ，[2,6,4] 和 [2] 。这是一个合法分割，因为 ik-1 - i1 等于 5 - 2 = 3 ，等于 dist 。总代价为 nums[0] + nums[2] + nums[5] ，也就是 1 + 2 + 2 = 5 。
5 是分割成 3 个子数组的最小总代价。

示例 2：

输入：nums = [10,1,2,2,2,1], k = 4, dist = 3
输出：15
解释：将数组分割成 4 个子数组的最优方案是：[10] ，[1] ，[2] 和 [2,2,1] 。这是一个合法分割，因为 ik-1 - i1 等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。
分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 ik-1 和 i1 的差为 5 - 1 = 4 ，大于 dist 。
15 是分割成 4 个子数组的最小总代价。

示例 3：

输入：nums = [10,8,18,9], k = 3, dist = 1
输出：36
解释：将数组分割成 4 个子数组的最优方案是：[10] ，[8] 和 [18,9] 。这是一个合法分割，因为 ik-1 - i1 等于 2 - 1 = 1 ，等于 dist 。总代价为 nums[0] + nums[1] + nums[2] ，也就是 10 + 8 + 18 = 36 。
分割 [10] ，[8,18] 和 [9] 不是一个合法分割，因为 ik-1 和 i1 的差为 3 - 1 = 2 ，大于 dist 。
36 是分割成 3 个子数组的最小总代价。

说明：

• 3 <= n <= 10^5
• 1 <= nums[i] <= 10^9
• 3 <= k <= n
• k - 2 <= dist <= n - 2

思路

定义数组的代价是其第一个元素值，有一个数组 nums，将其分割成 k 个连续且不相交的子数组，并且要求第 2 个子数组 与 第 k 个子数组的第一个元素的下标的距离不超过 dist，求子数组的最小总代价。

//todo

代码

性能

目标

给你一个数组 nums，你可以执行以下操作任意次数：

• 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
• 用它们的和替换这对元素。

返回将数组变为 非递减 所需的 最小操作次数 。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。

说明：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

提示：

• We can perform the simulation using data structures.
• Maintain an array index and value using a map since we need to find the next and previous ones.
• Maintain the indices to be removed using a hash set.
• Maintain the neighbor sums with the smaller indices (set or priority queue).
• Keep the 3 structures in sync during the removals.

思路

代码

性能

目标

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域只 统计一次 。

示例 1：

输入： squares = [[0,0,1],[2,2,1]]
输出： 1.00000
解释：
任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

示例 2：

输入： squares = [[0,0,2],[1,1,1]]
输出： 1.00000
解释：
由于蓝色正方形和红色正方形有重叠区域且重叠区域只统计一次。所以直线 y = 1 将正方形分割成两部分且面积相等。

说明：

• 1 <= squares.length <= 5 * 10^4
• squares[i] = [xi, yi, li]
• squares[i].length == 3
• 0 <= xi, yi <= 10^9
• 1 <= li <= 10^
• 所有正方形的总面积不超过 10^15。

思路

代码

性能