从Leetcode 每日一题练习继续讨论：
2375. 根据模式串构造最小数字
2375. Construct Smallest Number From DI String
题解
本题考虑数组遍历时只能向一个方向遍历，如果从前向后遍历则无法预知后面要给几个D预留出足够大小的数字，即无法拿到后面的关键信息，因此需要遍历两次来获取完整的信息，第一次从后向前遍历，记录连续出现的D的个数，当遇到I时将D的个数赋值给对应位置并将记录的个数清零，这样相当于通知当在这个位置增加数字大小时要提前预留出后面的D个数的大小空间。
再正向遍历数组，同样也要统计从前一个I到下一个I之间的D的个数m(考虑123546这样的字符串，对于4来说增加的时候不能仅仅加1，还要加上前方减掉的数字大小，因为减掉的这一区间的所有数字已经被使用了，因此我们要恢复到未减数字之前的值并基于此继续向上增加)，遇到I时将当前数字加1再增加记录的预留D的个数和m得到下一个值并将m清零。遇到D则将当前数字减一，最终可得满足条件的字符串。因为每次放置数字时都放置了当前位置可能的最小数字，因此这样得到的字符串是字典序最小的
代码
class Solution {
public:
string smallestNumber(string pattern) {
int len = pattern.size();
vector<int> reverse(len,0);
int dsum = 0;
for(int i=len-1;i>=0;i--){
if(pattern[i] == 'D'){
dsum++;
}else{
if(dsum > 0){
reverse[i] = dsum;
dsum = 0;
}
}
}
char current = '1'+dsum;
string result;
result += current;
int addD = 0;
for(int i=0;i<len;i++){
if(pattern[i] == 'I'){
current = current + 1 + reverse[i] + addD;
addD = 0;
result += current;
}else{
addD++;
current -= 1;
result += current;
}
}
return result;
}
};