smallest permutation from signature i,d

https://www.careercup.com/question?id=14912744

You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,....n]. Write the below function in language of your choice.

vector* FindPermute(const string& signature);

int lasti=1
For i = 1...siglen
    If signature[i] == 'I'
        print reverse(lasti, i)
        lasti=i+1
print reverse(lasti, siglen)

reverse(1,1) is 1, and reverse(4,6) is 654.
The pseudocode works in linear time and constant space, and uses 1 based indexing, which is why the indexing looks kind of strange. It is equivalent to starting with a list 1234567...n, finding all groups of Ds, and reversing sections of the initial list that the Ds overlap.

This greedy algorithm stems from the idea that if the list starts with an I, the output must start with a 1, if it starts with a single D, it must start 21, DD, 321 and so forth. Whenever it sees an I, it picks the minimum element that can be placed, and is therefore lexicographically minimal.

from sys import stdin

def solve(sign):
    result = []
    last = 1
    for i in range(1, len(sign) + 1):
        if sign[i - 1] == 'I':
            result += range(i, last - 1, -1)
            last = i + 1
    return result += range (len(sign) + 1, last - 1, -1)

for line in stdin.readlines(): 

    print solve(line[:-1]) http://www.1point3acres.com/bbs/thread-138432-1-1.html
Give a list of numbers:. From 1point 3acres bbs
3, 5, 9, 2
Generate a signature for the list of numbers:
i, i, d

Example:
6, 8, 3, 5, 2
i,d,i,d

Question is:. 鍥磋鎴戜滑@1point 3 acres
Given a signature for a list of number, trying to print out a list of number that fits the signature, with lowest value of the highest number, and at the same time, no duplicated numbers.
Numbers[1, N]

1,...n 可以满足任何 长度为n-1 的 类似于 ddididid 这样的wiggle sequence，问题是如何构造。

我用的的是链表，如果当前的字符是i，就把数字放到最后，如果是d，就把当前数字放到最近的i的位置

时间O(n) 空间O(1) (如果结果可以用链表表示的话)，应该是最优解吧

1.     public void findWiggle(String path) {
2.         ListNode fakeHead = new ListNode(0);
3.         //start from 1
4.         fakeHead.next = new ListNode(1);
5.         ListNode iInsert = fakeHead.next;
6.         ListNode dInsert = fakeHead;
7.         for (int i = 0; i < path.length(); i++) {
8.             if (path.charAt(i) == 'i') {
9.                 iInsert.next = new ListNode(i+2);
10.                 iInsert = iInsert.next;
11.                 dInsert = dInsert.next;
12.             } else {
13.                 ListNode tmp =  dInsert.next;
14.                 dInsert.next = new ListNode(i+2);. more info on 1point3acres.com
15.                 dInsert.next.next = tmp;
16.             }
17.         } 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
18.         print(fakeHead.next);
19.     }