# 484  Find Permutation

## 484. [Find Permutation](https://leetcode.com/problems/find-permutation/description/)

## 1. **Question**

By now, you are given a **secret signature** consisting of character 'D' and 'I'. 'D' represents a decreasing relationship between two numbers, 'I' represents an increasing relationship between two numbers. And our **secret signature** was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature "DI" can be constructed by array \[2,1,3] or \[3,1,2], but won't be constructed by array \[3,2,4] or \[2,1,3,4], which are both illegal constructing special string that can't represent the "DI"**secret signature**.

On the other hand, now your job is to find the lexicographically smallest permutation of \[1, 2, ... n] could refer to the given **secret signature** in the input.

**Example 1:**

```
Input: "I"

Output:
[1,2]

Explanation:
[1,2] is the only legal initial spectial string can construct secret signature "I", where the number 1 and 2 construct an increasing relationship.
```

**Example 2:**

```
Input: "DI"

Output: [2,1,3]

Explanation:
Both [2,1,3] and [3,1,2] can construct the secret signature "DI", 
but since we want to find the one with the smallest lexicographical permutation, you need to output [2,1,3]
```

## 2. **Implementation**

**(1) Two Pointers**

思路:

假设 input String = "DDID"

```
   原数组为         1 2 3 4 5

   变换后得          3 2 1 5 4
```

通过观察例子我们可以看到，string的\[0,1]上有两个D，而对应的数组\[0, 2]的数字被reversed. 同样，string在\[3]上有D，而nums对应的位置\[3,4]的数字也reversed，**所以当D在string\[i, j], i <= j出现时， 对应的nums数组在\[i, j + 1]的数字要reverse**

```java
class Solution {
    public int[] findPermutation(String s) {
        int n = s.length();

        int[] res = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            res[i] = i + 1;
        }

        int i = 0;
        while (i < n) {
            if (s.charAt(i) == 'D') {
                int j = i;

                while (j < n && s.charAt(j) == 'D') {
                    ++j;
                }
                reverse(res, i, j);
                i = j;
            }
            ++i;
        }
        return res;
    }

    public void reverse(int[] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            ++i;
            --j;
        }
    }
}
```

**(2) Stack:**

思路和上一种做法类似，只不过我们是通过stack达到reverse的效果。注意在最后我们要在stack加上s.length() + 1这个数

```java
class Solution {
    public int[] findPermutation(String s) {
        int n = s.length();
        int[] res = new int[n + 1];

        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == 'D') {
                stack.push(i);
            }
            else {
                stack.push(i);
                while (!stack.isEmpty()) {
                    res[j] = stack.pop();
                    ++j;
                }
            }
        }
        stack.push(n + 1);
        while (!stack.isEmpty()) {
            res[j] = stack.pop();
            ++j;
        }
        return res;
    }
}
```

## 3. **Time & Space Complexity**

**Two Pointers:** 时间复杂度O(n), 空间复杂度O(1)

**Stack:** 时间复杂度O(n), 空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/stack/484-find-permutation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.