代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
由范围 [1,n] 内所有整数组成的 n 个整数的排列 perm 可以表示为长度为 n - 1 的字符串 s ，其中:
perm[i] < perm[i + 1] ，那么 s[i] == ' i '
perm[i] > perm[i + 1] ，那么 s[i] == 'D' 。给定一个字符串 s ，重构字典序上最小的排列 perm 并返回它。
示例 1：
输入： s = "I" 输出： [1,2] 解释： [1,2] 是唯一合法的可以生成秘密签名 "I" 的特定串，数字 1 和 2 构成递增关系。
示例 2：
输入： s = "DI" 输出： [2,1,3] 解释： [2,1,3] 和 [3,1,2] 可以生成秘密签名 "DI"， 但是由于我们要找字典序最小的排列，因此你需要输出 [2,1,3]。
提示：
1 <= s.length <= 105s[i] 只会包含字符 'D' 和 'I'。方法一：贪心
先初始化结果数组 ans 为 [1, 2, 3, ..., n+1]。
假定某个连续 D 子数组区间为 [i, j)，那么只要翻转 ans[i: j + 1] 即可。
因此，遍历字符串 s，找出所有的连续 D 子数组区间，将其翻转。
时间复杂度 $O(n)$，其中 $n$ 表示字符串 s 的长度。
class Solution:
def findPermutation(self, s: str) -> List[int]:
n = len(s)
ans = list(range(1, n + 2))
i = 0
while i < n:
j = i
while j < n and s[j] == 'D':
j += 1
ans[i: j + 1] = ans[i: j + 1][::-1]
i = max(i + 1, j)
return ans
class Solution {
public int[] findPermutation(String s) {
int n = s.length();
int[] ans = new int[n + 1];
for (int i = 0; i < n + 1; ++i) {
ans[i] = i + 1;
}
int i = 0;
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == 'D') {
++j;
}
reverse(ans, i, j);
i = Math.max(i + 1, j);
}
return ans;
}
private void reverse(int[] arr, int i, int j) {
for (; i < j; ++i, --j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}
class Solution {
public:
vector<int> findPermutation(string s) {
int n = s.size();
vector<int> ans(n + 1);
iota(ans.begin(), ans.end(), 1);
int i = 0;
while (i < n) {
int j = i;
while (j < n && s[j] == 'D') {
++j;
}
reverse(ans.begin() + i, ans.begin() + j + 1);
i = max(i + 1, j);
}
return ans;
}
};
func findPermutation(s string) []int {
n := len(s)
ans := make([]int, n+1)
for i := range ans {
ans[i] = i + 1
}
i := 0
for i < n {
j := i
for ; j < n && s[j] == 'D'; j++ {
}
reverse(ans, i, j)
i = max(i+1, j)
}
return ans
}
func reverse(arr []int, i, j int) {
for ; i < j; i, j = i+1, j-1 {
arr[i], arr[j] = arr[j], arr[i]
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
