659. Split Array into Consecutive Subsequences 发表于 2022-01-18 Priority Queue1234567891011121314151617181920212223242526class 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; }} Greedy1234567891011121314151617181920212223242526272829303132333435class 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; }} Reference659. Split Array into Consecutive Subsequences