【字符串, 贪心】根据模式串构造最小数字

题目

2375. 根据模式串构造最小数字
484. 寻找排列

---

给你下标从 0 开始、长度为 n 的字符串 pattern ，它包含两种字符，'I' 表示 上升 ，'D' 表示 下降 。

你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件：

• num 包含数字 '1' 到 '9' ，其中每个数字 至多 使用一次。
• 如果 pattern[i] == 'I' ，那么 num[i] < num[i + 1] 。
• 如果 pattern[i] == 'D' ，那么 num[i] > num[i + 1] 。

请你返回满足上述条件字典序 最小 的字符串 num。

示例 1：

输入：pattern = "IIIDIDDD"
输出："123549876"
解释：
下标 0 ，1 ，2 和 4 处，我们需要使 num[i] < num[i+1] 。
下标 3 ，5 ，6 和 7 处，我们需要使 num[i] > num[i+1] 。
一些可能的 num 的值为 "245639871" ，"135749862" 和 "123849765" 。
"123549876" 是满足条件最小的数字。
注意，"123414321" 不是可行解因为数字 '1' 使用次数超过 1 次。

示例 2：

输入：pattern = "DDD"
输出："4321"
解释：
一些可能的 num 的值为 "9876" ，"7321" 和 "8742" 。
"4321" 是满足条件最小的数字。

提示：

• 1 <= pattern.length <= 8
• pattern 只包含字符 'I' 和 'D' 。

解题

方法一：贪心

思路

首先考虑一个极端情况：当 pattern 中全为 'I' 时，构造出来的字符串应该是 "1234……"，而当 pattern 中出现一段 'D' 的时候，为了保证构造出的字符串字典序最小，需要从这一段中第一个 'D' 出现的位置到最后一个 'D' 出现的位置填充逆序的数字，举个例子：

如果 pattern = "IIIDDD"，那么：

按照这个思路可以想出很多种构造字符串的方法，我们这里选择逆序部分字符串：

看图可以发现规律，最终构造出的字符串 "1237654" 可以看作是把字符串 "1234567" 的 "4567" 部分逆序而成的。

那么就可以找到规律：对于长度为 n 的 pattern 可以先初始化一个 1~n+1 的字符串(ans)(长度为 n+1)，然后遍历 pattern 找到每一段逆序部分的开始(start)和结束(end)索引，然后把 ans 的 start 到 end+1 部分逆序即可。

---

参考：【力扣周赛 306】数位 DP 通用模板 | LeetCode 算法刷题 - 第三题 贪心 优雅做法

代码

class Solution {
    char[] ans;

    public String smallestNumber(String pattern) {
        int n = pattern.length();
        ans = new char[n + 1];
        for (int i = 0; i <= n; ++i) ans[i] = (char) (i + '1');
        for (int i = 0; i < n; ++i) {
            if (pattern.charAt(i) == 'D') {
                int start = i;
                while (i < n && pattern.charAt(i) == 'D') ++i;
                reversePart(start, i);
            }
        }
        return String.valueOf(ans);
    }

    void reversePart(int start, int end) {
        while (start < end) {
            char tmp = ans[start];
            ans[start] = ans[end];
            ans[end] = tmp;
            ++start;
            --end;
        }
    }
}

class Solution {
public:
    string smallestNumber(string pattern) {
        int n = pattern.length();
        string ans;
        ans.resize(n + 1);
        for (int i = 0; i <= n; ++i) ans[i] = i + '1';
        for (int i = 0; i < n; ++i) {
            if (pattern[i] == 'D') {
                int start = i;
                while (i < n && pattern[i] == 'D') ++i;
                reverse(ans.begin() + start, ans.begin() + i + 1);
            }
        }
        return ans;
    }
};