LeetCode 1375. 二进制字符串前缀一致的次数

Categories:

题目描述
思路分析
1. 解法一：前缀最大值（推荐）
相似题目

题目描述

✅ 1375. 二进制字符串前缀一致的次数

思路分析

解法一：前缀最大值（推荐）

核心思路：

记录当前已翻转位置的最大下标 maxPos。

当 maxPos == i + 1 时，说明前 i+1 个位置都已翻转。

统计满足条件的次数。

复杂度分析：

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

空间复杂度：O(1)。

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int maxPos = 0;
        int res = 0;

        for (int i = 0; i < flips.length; i++) {
            if (flips[i] > maxPos) {
                maxPos = flips[i];
            }
            if (maxPos == i + 1) {
                res++;
            }
        }

        return res;
    }
}

func numTimesAllBlue(flips []int) int {
	maxPos := 0
	res := 0

	for i, v := range flips {
		if v > maxPos {
			maxPos = v
		}
		if maxPos == i+1 {
			res++
		}
	}

	return res
}

相似题目

题目	难度	考察点
1375. 二进制字符串前缀一致的次数	中等	前缀统计
1893. 检查是否区域内所有整数都被覆盖	简单	前缀统计
525. 连续数组	中等	前缀和
930. 和相同的二元子数组	中等	前缀和
1423. 可获得的最大点数	中等	前缀/滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/98843001