巨硬第四轮挂经

这道题好难呀。。。现在面这么难的题么

index1=last none 0 index
index2=last none 9 index && index2 < index1
arr[index1]--;
arr[index2]++;
counting sort on (index2, index1]

补充内容 (2021-08-21 22:44 +8:00):
上面这个有bug，重新来一个：
index1=last none 0 index
index2=last none 9 index && index2 < index1
counting sort on [index2 + 1, index1]
arr[index2]++;
arr[index2 + 1]--;

zhiyazw 发表于 2021-07-31 09:02:38
index1=last none 0 index
index2=last none 9 index && index2 < index1
arr--;

Bingo

想法是拿一个低位-1， 去把一个高位+1. 比如 5436, 换成5445
edge case: 低位是0, 找下一个非0低位
高位是9，需要进位完，对后面重新排序，后面非0最高位-1。
比如199->299->289，1990->2099->2089  

这题就是个生推题啊，感觉面试的时候一紧张很难想出来