659. Split Array into Consecutive Subsequences

Question

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

• Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
• All subsequences have a length of 3** or more**.

Return true* if you can split nums according to the above conditions, or false otherwise*.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [<u>1</u>,2,<u>3</u>,4,<u>5</u>] while [1,3,2] is not).

Solution

用优先级队列储存每个可组成的列表。
优先级队列根据列表的长度排列。

用哈希表记录每个列表的尾数，和其对应的优先级队列。
遍历所有数字，如果存在当前数字num-1为尾数的队列，则获取长度最小的列表，并添加当前数字num在列表中。
然后将新的优先级队列放入哈希表中。

遍历整个哈希表中的数组，如果有数组的长度小于3，则返回false，否则返回true。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<List<Integer>>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<List<Integer>> last = map.getOrDefault(num - 1, null);
            PriorityQueue<List<Integer>> curr = map.getOrDefault(num, new PriorityQueue<List<Integer>>((a,b) -> a.size() - b.size()));

            if(last == null || last.size() == 0){
                List<Integer> arr = new ArrayList<>();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
            else{
                List<Integer> arr = last.poll();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(List<Integer> arr : map.get(last)){
                if(arr.size() < 3) return false;
            }
        }
        return true;
        
    }
}

Solution 2

不需要保存整个列表，只需要保存对应末尾数字的列表长度即可。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<Integer> last = map.getOrDefault(num - 1, null);
            PriorityQueue<Integer> curr = map.getOrDefault(num, new PriorityQueue<Integer>());

            if(last == null || last.size() == 0){
                curr.add(1);
                map.put(num, curr);
            }
            else{
                int min = last.poll();
                curr.add(min+1);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(int len : map.get(last)){
                if(len < 3) return false;
            }
        }
        return true;

    }
}