1375. Number of Times Binary String Is Prefix-Aligned¶
题目信息¶
- 题号:
1375
- 难度:
Medium
- 主题:
数组、前缀、模拟
- 原题:
- 重点:
长度为
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
解释:点亮后前缀长度为一。