659. Split Array into Consecutive Subsequences

,

Priority Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, PriorityQueue<Integer>> lastNumberToQueueMap = new HashMap<>();
        for (int num : nums) {
            if (!lastNumberToQueueMap.containsKey(num)) {
                lastNumberToQueueMap.put(num, new PriorityQueue<>());
            }

            PriorityQueue<Integer> currQueue = lastNumberToQueueMap.get(num);
            PriorityQueue<Integer> prevQueue = lastNumberToQueueMap.get(num - 1);
            if (prevQueue == null || prevQueue.isEmpty()) {
                currQueue.add(1);
            } else {
                currQueue.add(prevQueue.poll() + 1);
            }
        }

        for (PriorityQueue<Integer> priorityQueue : lastNumberToQueueMap.values()) {
            if (priorityQueue != null && !priorityQueue.isEmpty() && priorityQueue.peek() < 3) {
                return false;
            }
        }

        return true;
    }
}

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> numberToCountMap = new HashMap<>();
        Map<Integer, Integer> lastNumberToSeqCountMap = new HashMap<>();

        for (int num : nums) {
            numberToCountMap.put(num, numberToCountMap.getOrDefault(num, 0) + 1);
        }

        for (int num : nums) {
            int count = numberToCountMap.getOrDefault(num, 0);
            if (count > 0) {
                if (lastNumberToSeqCountMap.getOrDefault(num - 1, 0) > 0) {
                    // 如果存在 num - 1 的子序列，则追加到后面，避免新建子序列
                    numberToCountMap.put(num, count - 1);
                    lastNumberToSeqCountMap.put(num - 1, lastNumberToSeqCountMap.get(num - 1) - 1);
                    lastNumberToSeqCountMap.put(num, lastNumberToSeqCountMap.getOrDefault(num, 0) + 1);
                } else {
                    // 新建子序列，检查能否创建长度大于等于 3 的子序列，如果不能直接返回 false
                    int count2 = numberToCountMap.getOrDefault(num + 1, 0), count3 = numberToCountMap.getOrDefault(num + 2, 0);
                    if (count2 < 1 || count3 < 1) {
                        return false;
                    } else {
                        numberToCountMap.put(num, count - 1);
                        numberToCountMap.put(num + 1, count2 - 1);
                        numberToCountMap.put(num + 2, count3 - 1);
                        lastNumberToSeqCountMap.put(num + 2, lastNumberToSeqCountMap.getOrDefault(num + 2, 0) + 1);
                    }
                }
            }
        }

        return true;
    }
}

References

659. Split Array into Consecutive Subsequences