题目内容

给定一个长度为 $n-1$ 的 $01$ 字符串，要求构建一个从 $1$ 到 $n$ 各出现一次的长度为 $n$ 的排列。字符串的第 $i$ 位为 $0$ 表示排列第 $i+1$ 位比第 $i$ 位小，反之，第 $i$ 位为 $1$ 表示排列第 $i+1$ 位比第 $i$ 位大。

输入描述

题解

题面描述

给定一个长度为 $n-1$ 的 $01$ 字符串，要求构建一个从 $1$ 到 $n$ 各出现一次的长度为 $n$ 的排列。字符串的第 $i$ 位为 $0$ 表示排列第 $i+1$ 位比第 $i$ 位小，反之，第 $i$ 位为 $1$ 表示排列第 $i+1$ 位比第 $i$ 位大。

思路

本题要求根据给定的 $01$ 字符串构造一个排列，使得排列中相邻元素的大小关系与字符串中的 $0$ 和 $1$ 对应。具体来说，字符串中的 $0$ 表示排列中后一个元素比前一个元素小，$1$ 表示后一个元素比前一个元素大。通过使用双指针策略，分别指向当前可用的最小数和最大数，根据字符串的字符动态选择当前元素的值，可以高效地构造出满足条件的排列。这种方法的时间复杂度为 $O(n)$，适用于大规模数据。