题解
题面描述
给定一个长度为 n−1 的 01 字符串，要求构建一个从 1 到 n 各出现一次的长度为 n 的排列。字符串的第 i 位为 0 表示排列第 i+1 位比第 i 位小，反之，第 i 位为 1 表示排列第 i+1 位比第 i 位大。
思路
本题要求根据给定的 01 字符串构造一个排列，使得排列中相邻元素的大小关系与字符串中的 0 和 1 对应。具体来说，字符串中的 0 表示排列中后一个元素比前一个元素小，1 表示后一个元素比前一个元素大。通过使用双指针策略，分别指向当前可用的最小数和最大数，根据字符串的字符动态选择当前元素的值，可以高效地构造出满足条件的排列。这种方法的时间复杂度为 O(n)，适用于大规模数据。
题目内容
音乐家记录了一段旋律的起伏，但忘记了具体的音高。旋律由 n 个音符组成，每个音符的音高是 1 到 n 的一个整数，且 n 个音高互不相同。他手头只有一段长度为 n−1 的记号，每个记号是 0 或 1：若第 i 个记号为 0，表示第 i+1 个音符的音高低于第 i 个音符；若为 1，则表示第 i+1 个音符的音高高于第 i 个音符。给定这段记号，请你还原任意一组合法的音高序列。
记号字符串的长度为 n−1，其中 2≤n≤105。保证输入数据总能构造出至少一组合法序列。
输入描述
输入共一行，包含一个由字符 0 和 1 组成的字符串（长度在 1 到 105 之间），表示相邻音符的升降关系。
输出描述
输出一行，包含 n 个以空格分隔的整数，表示还原出的音高序列。如果存在多种方案，输出任意一种即可。
