Medium

题目描述

给你一个长度为 n 的下标从 0 开始的二进制数组 nums。nums 可以按下标 i（其中 0 <= i <= n）分割成两个数组（可能为空）numsleft 和 numsright：

  • numsleft 包含 nums 中从下标 0 到 i - 1（包含）的所有元素，而 numsright 包含 nums 中从下标 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。

示例 2：

输入：nums = [0,0,0]
输出：[3]

示例 3：

输入：nums = [1,1]
输出：[0]

约束：

  • n == nums.length
  • 1 <= n <= 10^5
  • nums[i] 为 0 或 1

解题思路

这道题的核心思路是计算每个分割点的分数，分数 = 左侧0的个数 + 右侧1的个数。

基本思路： 我们可以预先计算数组中1的总个数，然后从左到右遍历数组：

  • 维护左侧0的个数（leftZeros）
  • 计算右侧1的个数 = 总1个数 - 左侧1个数（totalOnes - leftOnes）
  • 当前分割点的分数 = leftZeros + rightOnes

优化思路： 注意到当我们从位置 i 移动到位置 i+1 时：

  • 如果 nums[i] == 0，左侧0的个数增加1
  • 如果 nums[i] == 1，左侧1的个数增加1，右侧1的个数减少1

我们可以用一个变量 score 来追踪当前分数：

  • 如果遇到0，分数+1（左侧0增加）
  • 如果遇到1，分数-1（右侧1减少）

算法步骤：

  1. 计算初始分数：右侧所有1的个数
  2. 遍历数组，动态更新分数
  3. 记录最大分数和对应的所有下标

时间复杂度 O(n)，空间复杂度 O(1)（除了结果数组）。

代码实现

class Solution {
public:
    vector<int> maxScoreIndices(vector<int>& nums) {
        int n = nums.size();
        int totalOnes = 0;
        for (int num : nums) {
            totalOnes += num;
        }
        
        int score = totalOnes; // 初始分数：左侧0个，右侧totalOnes个1
        int maxScore = score;
        vector<int> result = {0};
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                score++; // 左侧0增加1
            } else {
                score--; // 右侧1减少1
            }
            
            if (score > maxScore) {
                maxScore = score;
                result = {i + 1};
            } else if (score == maxScore) {
                result.push_back(i + 1);
            }
        }
        
        return result;
    }
};

class Solution:
    def maxScoreIndices(self, nums: List[int]) -> List[int]:
        n = len(nums)
        total_ones = sum(nums)
        
        score = total_ones  # 初始分数：左侧0个，右侧total_ones个1
        max_score = score
        result = [0]
        
        for i in range(n):
            if nums[i] == 0:
                score += 1  # 左侧0增加1
            else:
                score -= 1  # 右侧1减少1
            
            if score > max_score:
                max_score = score
                result = [i + 1]
            elif score == max_score:
                result.append(i + 1)
        
        return result

public class Solution {
    public IList<int> MaxScoreIndices(int[] nums) {
        int n = nums.Length;
        int totalOnes = 0;
        foreach (int num in nums) {
            totalOnes += num;
        }
        
        int score = totalOnes; // 初始分数：左侧0个，右侧totalOnes个1
        int maxScore = score;
        IList<int> result = new List<int> { 0 };
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                score++; // 左侧0增加1
            } else {
                score--; // 右侧1减少1
            }
            
            if (score > maxScore) {
                maxScore = score;
                result = new List<int> { i + 1 };
            } else if (score == maxScore) {
                result.Add(i + 1);
            }
        }
        
        return result;
    }
}

var maxScoreIndices = function(nums) {
    const n = nums.length;
    const totalOnes = nums.reduce((sum, num) => sum + num, 0);
    
    let score = totalOnes; // 初始分数：左侧0个，右侧totalOnes个1
    let maxScore = score;
    let result = [0];
    
    for (let i = 0; i < n; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n)需要遍历数组两次：一次计算总1数，一次计算各分割点分数
空间复杂度O(1)只使用常数额外空间，不计算结果数组

相关题目