Back to Leetcode

Readme

Greedy/3863.Minimum-Operations-to-Sort-a-String/Readme.md

latest1.2 KB
Original Source

3863.Minimum-Operations-to-Sort-a-String

此题有明显的贪心策略,最多三次操作一定能够实现有序:先将[1,n-1]排序,然后将[2,n]排序,此时保证全局的最大值一定已经放在了队尾;最后再将[1,n-1]排序,就保证了全局有序。

事实上,如果不必须将首元素搬运至队尾(即首元素不是全局唯一最大值),那么两次操作即可:先做后面[2,n]的排序,再做前面[1,n-1]的排序。这样保证了全局最小值一定能放在队首,并且[2,n]已经是有序的。

同理,如果不必须将尾元素搬运至队首(即尾元素不是全局唯一最小值),那么两次操作即可:先做前面[1,n-1]的排序,再做后面[2,n]的排序。这样保证了全局最大值一定能放在队尾,并且[1,n-1]已经是有序的。

另外,也有需要更少操作的情况。

  1. 如果s只有两个元素且是逆序的,那么无解。
  2. 如果s已经有序,那么操作数是0.
  3. 如果s的首元素已经是全局最小,那么只需要将[2,n]排序即可;或者反之,如果s的尾元素已经是全局最大,那么只需要将[1,n-1]排序即可。这两种情况只需要1次操作。