484. Find Permutation

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:

• s[i] == ‘I’ if perm[i] < perm[i + 1], and
• s[i] == ‘D’ if perm[i] > perm[i + 1].

Given a string s, reconstruct the lexicographically smallest permutation perm and return it.

Example 1:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

Example 2:

Input: s = "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3]

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either ‘I’ or ‘D’.

Code

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

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

        int i = 0;
        while(i < s.length()){
            if (s.charAt(i) == 'I') {
                i++;
                continue;
            }
            
            int head = i;
            
            while (i < s.length() && s.charAt(i) == 'D'){
                i++;
            }
            
            reverse(res, head, i);
        }
        
        return res;
    }
    
    private void reverse(int[] nums, int i, int j){
        int left = i;
        int right = j;
        
        while (left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}