Uber OA 平衡排列：1..k 是否占据连续位置

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入是 1..n 的排列，每个数恰好出现一次；结果第 k 位表示是否有一个长度 k 的连续子数组正好包含 1..k。
• 当文字定义与示例冲突时，以文字定义为训练契约，并明确列出冲突；真实 OA 须以现场官方测试或面试官澄清为准。
• 空排列返回空字符串；非排列输入报错，避免 min/max 跨重复值的错误推断。

解题路线

1. 预处理每个值在排列中的位置 pos[value]。逐步把 1、2、…、k 的位置加入集合，只维护当前最小位置 lo 和最大位置 hi。
2. k 个不同位置能处在某个长度 k 的连续区间中，当且仅当 hi−lo+1=k；若跨度更大，中间必有不属于 1..k 的数。
3. 按 k 从 1 到 n 依次追加 1/0。每次只更新两个边界，完成全部 n 位。

手动走一遍

[4,3,1,2] 的位置分别是 pos[1]=2、pos[2]=3、pos[3]=1、pos[4]=0。k=1、2、3、4 的位置跨度分别为 1、2、3、4，故按文字规则是 1111。题目写 1011，与其 k=2 的 [1,2] 连续窗口直接矛盾。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""For each k, detect a contiguous block containing exactly values 1..k."""


def balanced_lengths(permutation: list[int]) -> str:
    n = len(permutation)
    if sorted(permutation) != list(range(1, n + 1)):
        raise ValueError("expected a permutation of 1..n")
    positions = [0] * (n + 1)
    for index, value in enumerate(permutation):
        positions[value] = index
    lo = n
    hi = -1
    answer = []
    for value in range(1, n + 1):
        lo = min(lo, positions[value])
        hi = max(hi, positions[value])
        answer.append("1" if hi - lo + 1 == value else "0")
    return "".join(answer)

复杂度

检查输入排列需排序 O(n log n)（示例代码的防御校验）；若题目保证是合法排列，可去掉校验，构建位置表和求答案都是 O(n) 时间、O(n) 空间。

易错点与追问

容易失分的边界

• 这里要求的是某个连续子数组包含 1..k，并不要求 1..k 在数组中升序排列。
• 只检查 min/max 值没有用；关键是这些值在原排列里的最左与最右位置。
• 题目 1011 样例不能据此反推出新规则，可能是誊录或输出错误；不能把推测写成原题。

继续深挖

• 若结果只需回答单个 k，扫描前 k 个值的位置即可 O(k)，多次查询时预处理所有答案。
• 若输入含重复值，跨度等于 k 不再是充分条件，需重新定义是否允许重复、每个值出现次数及窗口规则。