Google – Minimum Fluctuation Sequence
给一个String pattern, 包好两个字母i和d，i表示increase, d表示decrease, 生成一个最小的且满足pattern的数字，比如：
iii -> 1234
ddd -> 4321
iid -> 1243
每个数字不能重复使用。能重复使用的解法见后面follow up.
[Solution]
Greedy + Linked list
维护一个linked list来存每个digit，用一个pointer来指向最近一次碰到d的digit，一旦碰到i，pointer就指向tail.
[Note]
需要注意一下0这个特殊情况，因为第一个digit不能为0，所以pattern中第一个d肯定对应0。需要特殊处理一下。
Read full article from Google – Minimum Fluctuation Sequence
给一个String pattern, 包好两个字母i和d，i表示increase, d表示decrease, 生成一个最小的且满足pattern的数字，比如：
iii -> 1234
ddd -> 4321
iid -> 1243
每个数字不能重复使用。能重复使用的解法见后面follow up.
[Solution]
Greedy + Linked list
维护一个linked list来存每个digit，用一个pointer来指向最近一次碰到d的digit，一旦碰到i，pointer就指向tail.
[Note]
需要注意一下0这个特殊情况，因为第一个digit不能为0，所以pattern中第一个d肯定对应0。需要特殊处理一下。
class Solution { public int fluctuationSequence(String pattern) { if (pattern == null || pattern.isEmpty()) { return 0; } List<Integer> list = new LinkedList<>(); list.add(1); int next = 2; int idx = 0; boolean firstD = true; for (char c : pattern.toCharArray()) { if (c == 'i') { list.add(next); idx = list.size() - 1; } else if (firstD) { list.add(0); firstD = false; continue; } else { list.add(idx, next); } next++; } int result = 0; for (int num : list) { result = result * 10 + num; } return result; }}// digit能重复, candy解法class Solution2 { public int fluctuationSequence(String pattern) { if (pattern == null || pattern.isEmpty()) { return 0; } int[] nums = new int[pattern.length() + 1]; nums[0] = 1; int prev = 1; boolean firstD = true; for (int i = 0; i < pattern.length(); i++) { char c = pattern.charAt(i); if (c == 'i') { nums[i + 1] = prev + 1; prev = prev + 1; } else if (firstD) { nums[i + 1] = 0; prev = 0; firstD = false; } else if (prev == 0) { nums[i + 1] = 0; } else { nums[i + 1] = prev - 1; prev = prev - 1; } } for (int i = pattern.length() - 1; i >= 0; i--) { char c = pattern.charAt(i); if (c == 'i' && nums[i] >= nums[i + 1]) { nums[i + 1] = nums[i] + 1; } else if (c == 'd' && nums[i] <= nums[i + 1]) { nums[i] = nums[i + 1] + 1; } } int result = 0; for (int num : nums) { result = result * 10 + num; } return result; }}Read full article from Google – Minimum Fluctuation Sequence
