将一个字符串排序的最小操作次数网页链接力扣LeetCode力扣LeetCode 每日一题完成每日打卡即可获得力扣积分。获得相应数量的积分能在【力扣商店】换取相应奖品助力每日有题做丰盈积分日益多题目描述给你一个由小写英文字母组成的字符串s。在一次操作中你可以选择s的任意子字符串但不能是整个字符串并将其按非降序字母顺序进行排序。返回使s按非降序排列所需的最小操作次数。如果无法做到则返回-1。输入描述一个由小写英文字母组成的字符串s。输出描述返回使s按非降序排列所需的最小操作次数如果无法做到则返回-1。示例 1输入s dog输出1解释将子字符串og排序为go。现在s dgo已按升序排列。因此答案是1。示例 2输入s card输出2解释将子字符串car排序为acr得到s acrd。将子字符串rd排序为dr得到s acdr已按升序排列。因此答案是2。示例 3输入s gf输出-1解释在给定提示下无法对s进行排序。因此答案是-1。数据范围1 ≤ s.length ≤ 10 5 1 \le \text{s.length} \le 10^51≤s.length≤105s仅由小写英文字母组成解题思路本题是结论分类 构造性判定问题。一次操作只能选择一个真子串并升序排序因此答案只可能是0 , 1 , 2 , 3 0,1,2,30,1,2,3或− 1 -1−1。关键在于根据字符串中最小字符和最大字符的位置进行分类。设x xx为字符串中的最大字符y yy为字符串中的最小字符n nn为字符串长度。1. 已经有序若s本身已经非递减不需要任何操作返回0。2. 长度为 2 且未排序长度为2 22时唯一合法的真子串长度只能为1 11排序后字符串不变。因此若s未排序永远无法完成返回-1。3. 一次操作即可完成若满足以下任一条件s[0] y最小字符已经在开头只需将后缀s[1..n-1]排序整体即可非递减s[n-1] x最大字符已经在末尾只需将前缀s[0..n-2]排序整体即可非递减。由于此时字符串未排序答案恰好为1。4. 两次操作即可完成若最小字符y yy或最大字符x xx出现在中间位置即存在1 ≤ i ≤ n − 2 1 \le i \le n-21≤i≤n−2使得s[i] y或s[i] x则答案为2。构造方法若y yy在中间位置i ii先排序前缀s[0..i]把y yy移到开头再排序后缀s[1..n-1]使剩余部分有序若x xx在中间位置i ii先排序后缀s[i..n-1]把x xx移到末尾再排序前缀s[0..n-2]使剩余部分有序。由于前面已经排除了0 00次和1 11次的情况所以此时最小操作次数恰为2。5. 其余情况答案为 3排除以上情况后必有最小字符y yy不在开头、也不在中间因此只能在末尾最大字符x xx不在末尾、也不在中间因此只能在开头。即字符串形如x ⋯ y x \ \cdots \ yx⋯y其中x xx是最大字符y yy是最小字符。此时不能通过1 11次或2 22次操作完成但可以通过3 33次操作完成。例如依次排序s[0..n-2]把x xx移到前缀末尾排序s[1..n-1]把y yy移到后缀开头同时把x xx移到末尾排序s[0..n-2]把y yy移到整个字符串开头其余部分升序。最终整个字符串非递减因此答案为3。6. 复杂度分析求最大字符和最小字符O ( n ) O(n)O(n)判断是否已排序O ( n ) O(n)O(n)检查中间是否出现x xx或y yyO ( n ) O(n)O(n)。总时间复杂度为O ( n ) O(n)O(n)空间复杂度为O ( 1 ) O(1)O(1)。总结先统计最大字符x xx和最小字符y yy。根据y yy是否在开头、x xx是否在末尾、以及它们是否出现在中间将答案分为0 , 1 , 2 , 3 , − 1 0,1,2,3,-10,1,2,3,−1五类。每类都有对应的构造或不可能性证明因此只需线性扫描即可得到最小操作次数。代码内容classSolution{public:intminOperations(string s){charxa,yz;intns.length();for(inti0;in;i){xmax(x,s[i]);ymin(y,s[i]);}if(ranges::is_sorted(s)){return0;}if(n2){return-1;}if(s[0]y||s[n-1]x){return1;}for(inti1;in-1;i){if(s[i]y||s[i]x){return2;}}return3;}};