Lintcode：884. 寻找排列

现在，给你一个由字符'D'和'I'构成的加密签名。'D'表示两个数字是递减关系，'I'表示两个数字是递增关系。我们的加密签名是由一个特殊的整数数组生成的。这个数组含有从1到n（n是加密签名的长度加1）的所有数字，并且每个数字只出现一次。举例来说，加密签名"DI"可以有数组[2,1,3]或者[3,1,2]生成，但是不能由数组[3,2,4]或者[2,1,3,4]生成。[3,2,4]和[2,1,3,4]都不能生成"DI"这个特定的加密签名。

找到能够生成输入加密签名的[1, 2, ... n]的最小字典序的排列。

public int[] findPermutation(String s) {
    // write your code here
    int n = s.length();
    int lastD_pos = -1;
    int lastI_pos = -1;
    int[] arr = new int[n + 1];
    if (s.charAt(0) == 'D'){
        arr[0] = 2;
        arr[1] = 1;
        lastD_pos = 0;
    }else if(s.charAt(0) == 'I'){
        arr[0] = 1;
        arr[1] = 2;
        lastI_pos = 0;
    }

    int curMax = 2;

    for (int i = 1; i < n; i++) {
        if (s.charAt(i) == 'D') {
            lastD_pos = i;
            for (int j = lastI_pos; j < i; j++) {
                arr[j + 1] = arr[j + 1] + 1;
                curMax = Integer.max(arr[j+1], curMax);
            }
            arr[i + 1] = arr[i] - 1;
        }else if (s.charAt(i) == 'I'){
            lastI_pos = i;
            arr[i+1] = curMax + 1;
            curMax++;
        }
    }

    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i]+" ");
    }

    return arr;
}

dalao解法：

public int[] findPermutation2(String s) {
    // write your code here
    //对s进行遍历，先给I位置的数赋值，赋值之后给I前面的D赋逐渐减小的值
    int i = 0, j = 0;
    int[] ans = new int[s.length() + 1];
    while (j < s.length()) {
        if (s.charAt(j) == 'I') {
            ans[i] = j + 1;
            while (++i <= j) {
                ans[i] = ans[i-1] - 1;
            }
        }
        j++;
    }
    ans[i] = j + 1;
    while (++i <= j) {
        ans[i] = ans[i-1] - 1;
    }
    return ans;
}

这道题一开始最困扰的就是如果后一个字母是d，就会影响前面的排列，怎么消除这种影响，一直在想如果后面是d怎么解决，其实当时想复杂了，如果是d那么直接更新前面的排列，不要再想着如果后面一个还是d要怎么做，是不是该留出几个数字空位来给后面的d。其实这种想法完全多余，你根本管不了未来会发生什么，你只需要关心的是如果出现了d，该如何更新前面的序列，所以我的思路很简单，定义一个变量记录当前出现的最大数因为要在他的基础上加减，再定义一个变量记录上一次d出现的位置，因为更新的话会影响到上一个d

因此采取的贪心策略就是出现什么处理什么（感觉强行贪心，其实是因为不知道怎么总结）

dalao的思路就清晰的多

采用两根指针，贪心策略是先处理I的情况，进行遍历，先给I位置的数赋值，赋值之后给I前面的D赋逐渐减小的值
summary: 1.不要考虑以后会怎样，先处理好当下
2.有时候两种情况就意味着只需处理一种情况的同时就可以把另一种情况同时处理了

小蜜蜂

Lintcode：884. 寻找排列