https://gist.github.com/gcrfelix/24ab5d020b2b54e94483
First, "i" represents increase, "d" represents decrease, so for number 123, the sequence would be "ii", for number 87123, sequence would "ddii".
The question is to generate the minimum number follows given sequence "iidd".
解法: while loop,
step1, "" -> [1], next number for step2 is 2
step2 "i" -> [1, 2], next number for step3 is 3
step3 "i" -> [1, 2, 3], next number for step4 is 4
到第四步发现 [1, 2, 3, 4] 不符合 iid, 怎么办呢? 把4 与前面的3 交换 [1, 2, 4, 3] match "iid"
到第五步发现[1, 2, 4, 3, 5] 又不符合 iidd 怎么办呢? 把5与插到4前 [1, 2, 5, 4, 3].
这样12543 应该是最小的number了.
解法:
核心就是每次记录last decreasing point. insert next number before last decreasing point. 本来用string 做的,
然后有个小while loop to find last decreasing point. 后来小哥说用一个新的data structure 会快些。链表结构,
you just need to keep track of the node which is last decreasing point node
First, "i" represents increase, "d" represents decrease, so for number 123, the sequence would be "ii", for number 87123, sequence would "ddii".
The question is to generate the minimum number follows given sequence "iidd".
解法: while loop,
step1, "" -> [1], next number for step2 is 2
step2 "i" -> [1, 2], next number for step3 is 3
step3 "i" -> [1, 2, 3], next number for step4 is 4
到第四步发现 [1, 2, 3, 4] 不符合 iid, 怎么办呢? 把4 与前面的3 交换 [1, 2, 4, 3] match "iid"
到第五步发现[1, 2, 4, 3, 5] 又不符合 iidd 怎么办呢? 把5与插到4前 [1, 2, 5, 4, 3].
这样12543 应该是最小的number了.
解法:
核心就是每次记录last decreasing point. insert next number before last decreasing point. 本来用string 做的,
然后有个小while loop to find last decreasing point. 后来小哥说用一个新的data structure 会快些。链表结构,
you just need to keep track of the node which is last decreasing point node