class Solution {
public:
vector<int> maxScoreIndices(vector<int>& nums) {
}
};
2155. 分组得分最高的所有下标
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [0,0,1,0] 输出：[2,4] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。 - 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。 - 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。 - 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。 - 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。 下标 2 和 4 都可以得到最高的分组得分 3 。 注意，答案 [4,2] 也被视为正确答案。
示例 2：
输入：nums = [0,0,0] 输出：[3] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。 - 1 ：numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。 - 2 ：numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。 - 3 ：numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。 只有下标 3 可以得到最高的分组得分 3 。
示例 3：
输入：nums = [1,1] 输出：[0] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。 - 1 ：numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。 - 2 ：numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。 只有下标 0 可以得到最高的分组得分 2 。
提示：
n == nums.length1 <= n <= 105nums[i] 为 0 或 1原站题解
golang 解法, 执行用时: 316 ms, 内存消耗: 8.5 MB, 提交时间: 2022-11-28 14:20:36
func maxScoreIndices(nums []int) []int {
left, right := 0, 0
for i := len(nums) - 1; i >= 0; i-- {
right += nums[i] // 先算出整个数组的 1 的个数
}
maxSum := right
ans := []int{0}
for i, v := range nums {
left += v ^ 1 // 不断增加左边 0 的个数
right -= v // 减少右边 1 的个数
if left+right > maxSum { // 更新答案
maxSum = left + right
ans = []int{i + 1}
} else if left+right == maxSum {
ans = append(ans, i+1)
}
}
return ans
}
golang 解法, 执行用时: 308 ms, 内存消耗: 8.6 MB, 提交时间: 2022-11-28 14:19:59
func maxScoreIndices(nums []int) []int {
n := len(nums)
presum, m, ans := 0, -1-n, []int{}
for i := 0; i <= n; i++ {
if cur := presum * 2 - i; cur > m {
m, ans = cur, []int{i}
} else if cur == m {
ans = append(ans, i)
}
if i < n && nums[i] == 0{
presum++
}
}
return ans
}
python3 解法, 执行用时: 292 ms, 内存消耗: 23.8 MB, 提交时间: 2022-11-28 14:19:33
class Solution:
def maxScoreIndices(self, nums: List[int]) -> List[int]:
# best 为历史最大值
presum = best = 0
# ans 为历史最大值的下标
ans = [0]
for i, num in enumerate(nums):
if num == 0:
presum += 1
if presum > best:
best = presum
ans = [i + 1]
elif presum == best:
ans.append(i + 1)
else:
presum -= 1
return ans