Given a permutation p of length n, a number k is balanced if there are two indices l, r (l <= r) such that the numbers p[l], p[l + 1], …, p[r] form a permutation of the numbers 1, 2, ..., k.
For each k (1 <= k <= n), determine if it is balanced.
Return a binary string of length n where the i-th character is '1' if i is balanced and '0' otherwise.
A permutation of length n contains each integer from 1 to n exactly once, in any order.
Example
n = 4
p = [4, 1, 3, 2]- For
k = 1: Choosel = 2,r = 2, sop[2:2] = [1], which is a permutation of length 1. - For
k = 2: No pair of indices results in a permutation of length 2, so it is not balanced. - For
k = 3: Choosel = 2,r = 4, sop[2:4] = [1, 3, 2], which is a permutation of length 3. - For
k = 4: Choosel = 1,r = 4, sop[1:4] = [4, 1, 3, 2], which is a permutation of length 4.
The balanced numbers are 1, 3, and 4, while 2 is not balanced. Therefore, the answer is 1011.
Function Description
Complete the function countBalancedNumbers in the editor below.
int p[n]: the given permutationReturns string: the binary string as described
这道题的关键是观察：如果某个前缀值集合 1..k 能在原数组中形成一个连续子数组，那么这 k 个数在位置上一定构成一个连续区间。做法是先记录每个数字在排列中的位置，然后从 1 到 n 逐步维护当前出现过的最小位置和最大位置；当这两个边界的长度刚好等于当前 k 时，说明 1..k 恰好覆盖了一个连续段，答案对应位记为 1，否则记为 0。整体只需一次线性扫描，时间复杂度 O(n)，适合 n 很大的排列题。
