1375. Number of Times Binary String Is Prefix-Aligned

题目信息

题号:

1375

难度:

Medium

主题:

数组、前缀、模拟

原题:

LeetCode 1375

重点:

长度为 n 的灯泡初始全灭,按排列 flips 依次点亮;某时刻所有已亮灯泡恰好构成从位置 1 开始的前缀时计数

题目重述

有 n 个编号 1 到 n 的灯泡,初始均关闭。第 i 步点亮位置 flips[i],数组 flips 是所有位置的一个排列,因此每个灯泡恰好点亮一次。

若完成某一步后,所有已经点亮的灯泡正好是位置 1 到 i+1,则该时刻前缀对齐。请返回前缀对齐出现的次数。

1 <= n <= 5 * 10^4。

自建示例

乱序点亮后可以多次重新对齐:

输入:flips = [2,1,3,5,4]
输出:3
解释:第 2、3、5 步后,已点亮位置分别为前 2、前 3、前 5 个位置。

只有一个灯泡时唯一一步必然对齐:

输入:flips = [1]
输出:1
解释:点亮后前缀长度为一。