[Leetcode] 1375. Number of Times Binary String Is Prefix-Aligned (Medium)

概述

題目

https://leetcode.com/problems/number-of-times-binary-string-is-prefix-aligned/
給一隨機由 1~n 組成的數列，求有多少前 i 位數是 prefix 包含 1~i

心得

幾個月前第一次看到題目覺得好像很難，但這次看過確認 max 值就似乎沒什麼難度

Max value

思路

走過一次數組，若是最大者 = 數組長度，則符合題意，最終計算數量

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def numTimesAllBlue(self, flips):
        """
        :type flips: List[int]
        :rtype: int
        """
        n = len(flips)
        mxv = 0
        cnt = 0
        for i in range(n):
            mxv = max(mxv, flips[i])
            if mxv == i+1:
                cnt += 1
        return cnt

Complexity

Time Complexity: O(n)
每個數只經過一次

Space Complexity: O(1)
只存 max 與 cnt 值