942.增减字符串匹配

增减字符串匹配

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

• 如果 perm[i] < perm[i + 1] ，那么 s[i] == ‘I’
• 如果 perm[i] > perm[i + 1] ，那么 s[i] == ‘D’

给定一个字符串 s ，返回 [0,n] 内所有整数的一个排列 perm 。

示例 1:

输入：s = “IDID”
输出：[0,4,1,3,2]

示例 2:

输入：s = “DDI”
输出：[3,2,0,1]

提示:

• 1 <= s.length <= 10^5
• s[i] 要么是 ‘I’，要么是 ‘D’

解析

使用双指针，’I’ 时取最小值，’D’ 时取最大值。

var diStringMatch = function (s) {
  let low = 0,
    high = s.length;
  const result = [];

  for (const c of s) {
    if (c === "I") {
      result.push(low++);
    } else {
      result.push(high--);
    }
  }

  result.push(low);
  return result;
};

时间复杂度 O(n)，空间复杂度 O(1)。