484. Find Permutation

 一刷 08/2022

Version #1 Stack

因为要保证最小，所以要reverse some subarray in the min array if we encountered a 'D'

因为在min array里面前面的element 永远是小于后面的element的，所以即使前面reverse，也一定满足I

我觉得难点在于'D''I'都是针对两个elements来说的，所以index的处理有点麻烦

Time O(N)

Space O(N)

Runtime: 15 ms, faster than 31.91% of Java online submissions for Find Permutation.

Memory Usage: 53.4 MB, less than 26.60% of Java online submissions for Find Permutation.

class Solution {

    public int[] findPermutation(String s) {

        int[] result = new int[s.length() + 1];

        int p = 0;

        int num = 1;

        Stack<Integer> stack = new Stack<>();

        // "DI"

        // 

        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == 'D') {

                stack.push(num++);

                continue;

            }

            stack.push(num++);

            while (!stack.isEmpty()) {

                result[p++] = stack.pop();

            }

        }

        stack.push(num);

        while (!stack.isEmpty()) {

            result[p++] = stack.pop();

        }

        return result;

    }

}