Question

484. 寻找排列

English Version

题目描述

由范围 [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 <= 105
• s[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]
  }
}