为何生成最小字典序数字的代码需从字符串末尾反向遍历？

题目要求 #

输入一个字符串，对于每个位置，可执行操作：删除该位数字，将min(9, s[i])插入字符串任意位置。求能得到的最小字典序数字。

用户困惑 #

为什么代码中的for循环要从字符串最后一位（size-1）开始反向遍历？尝试从开头遍历结果总是错误，请求解释原因。

参考代码 #

using namespace std;

void solve(){
    string s; 
    cin>>s;
    int size=s.size(); // 获取字符串长度
    char mn='9'; // 初始最小值设为'9'
    for(int i=size-1;i>=0;i--){     // 从最后一位开始反向遍历
            mn=min(mn,s[i]); // 更新当前位置到末尾的最小值
        if(s[i]!='9' && s[i]>mn){       // 当前数字不是9，且大于后面的最小值
            s[i]++;                 // 将当前数字加1
        }
    }
    sort(s.begin(),s.end());        // 排序得到最小字典序
    cout<<s<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        solve();
        }
        return 0;
}

反向遍历的核心原因 #

要理解这个逻辑，得先拆解题目操作的本质：

• 如果当前数字是9，执行操作（删9插9）后字符串无变化，无需处理。
• 如果当前数字不是9，执行操作等价于把当前数字替换为s[i]+1（删除原数字，插入min(9,s[i])=s[i]+1，字符串总长度不变）。

我们的目标是让最终排序后的字典序最小，关键判断逻辑是：如果当前数字后面存在比它更小的数字，就把当前数字加1。因为加1后的数字在排序时会被放到更靠后的位置，让更小的数字能前置，从而降低整体字典序。

反向遍历的作用就是实时维护当前位置到字符串末尾的最小值mn：

• 从最后一位开始，每遍历一个位置，就更新mn为当前mn和s[i]的最小值，这样mn始终代表当前位置右侧所有数字中的最小值。
• 如果正向遍历，我们还没遍历到后面的数字，无法知道当前位置右侧是否存在更小的数字，自然无法正确判断是否需要将当前数字加1。

举个例子，比如输入字符串"321"：

• 反向遍历到i=2（字符'1'）：mn更新为'1'，当前数字等于最小值，无需操作。
• 遍历到i=1（字符'2'）：mn还是'1'，'2' > '1'且不是9，所以'2'变为'3'。
• 遍历到i=0（字符'3'）：mn还是'1'，'3' > '1'且不是9，所以'3'变为'4'。
• 最终字符串变为"431"，排序后得到"134"，这是符合要求的最小字典序。

如果正向遍历，一开始mn是'9'，遍历到i=0时mn更新为'3'，当前数字等于mn，不操作；遍历到i=1时mn更新为'2'，也不操作；遍历到i=2时mn更新为'1'，还是不操作。最后排序得到"123"，这显然错误——因为我们错过了对'3'和'2'的优化操作。

内容的提问来源于stack exchange，提问作者dafslasd