LeetCode 1151. 最少交换次数来组合所有的 1

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

✅ 1151. 最少交换次数来组合所有的 1

思路分析

解法一：滑动窗口（推荐）

核心思路：

统计数组中 1 的总数，设为窗口大小。

在长度固定的窗口中统计 1 的最大数量。

需要交换的次数等于窗口大小减去最大 1 数量。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int minSwaps(int[] data) {
        int ones = 0;
        for (int val : data) {
            if (val == 1) {
                ones++;
            }
        }
        if (ones <= 1) {
            return 0;
        }

        int maxOnes = 0;
        int window = 0;
        for (int i = 0; i < data.length; i++) {
            window += data[i];
            if (i >= ones) {
                window -= data[i - ones];
            }
            if (i >= ones - 1) {
                maxOnes = Math.max(maxOnes, window);
            }
        }

        return ones - maxOnes;
    }
}

func minSwaps(data []int) int {
	ones := 0
	for _, val := range data {
		if val == 1 {
			ones++
		}
	}
	if ones <= 1 {
		return 0
	}

	maxOnes := 0
	window := 0
	for i := 0; i < len(data); i++ {
		window += data[i]
		if i >= ones {
			window -= data[i-ones]
		}
		if i >= ones-1 && window > maxOnes {
			maxOnes = window
		}
	}

	return ones - maxOnes
}

相似题目

题目	难度	考察点
1004. 最大连续1的个数 III	中等	滑动窗口
487. 最大连续1的个数 II	中等	滑动窗口
713. 乘积小于 K 的子数组	中等	滑动窗口
904. 水果成篮	中等	滑动窗口
209. 长度最小的子数组	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/70567385