LeetCode 1656. Design ordered flow

1656. Design ordered flow

Yes n individual (id, value) Yes , among id yes 1 To n An integer between ,value Is a string . non-existent id The same two (id, value) Yes .

Design a stream , With arbitrarily Sequential acquisition n individual (id, value) Yes , And when called many times Press id Increasing order Return some values .

Realization OrderedStream class ：

• OrderedStream(int n) Construct one that can receive n A stream of values , And put the current pointer ptr Set to 1 .

• String[] insert(int id, String value)
  

  Store new

  (id, value)
  

  Yes . After storage ：

  • If the stream store has id = ptr Of (id, value) Yes , Find out from id = ptr At the beginning The longest id A sequence of successive increments , and According to the order Back with these id List of associated values . then , take ptr Update to the last one id + 1 .
  • otherwise , Return an empty list .

Example ：

 Input 
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
 Output 
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

 explain 
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); //  Insert  (3, "ccccc"), return  []
os.insert(1, "aaaaa"); //  Insert  (1, "aaaaa"), return  ["aaaaa"]
os.insert(2, "bbbbb"); //  Insert  (2, "bbbbb"), return  ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); //  Insert  (5, "eeeee"), return  []
os.insert(4, "ddddd"); //  Insert  (4, "ddddd"), return  ["ddddd", "eeeee"]

Tips ：

• 1 <= n <= 1000
• 1 <= id <= n
• value.length == 5
• value It's only made up of lowercase letters
• Every time you call insert Will use a unique id
• Just call n Time insert

Two 、 Method 1

class OrderedStream {
    
    private int ptr = 1;
    private final String[] strs;
    public OrderedStream(int n) {
    
        strs = new String[n + 1];
    }
    
    public List<String> insert(int idKey, String value) {
    
        strs[idKey] = value;
        List<String> res = new ArrayList<>();
        while (ptr < strs.length && strs[ptr] != null) {
    
            res.add(strs[ptr]);
            ptr++; 
        }
        return res;
    }
}

/** * Your OrderedStream object will be instantiated and called as such: * OrderedStream obj = new OrderedStream(n); * List<String> param_1 = obj.insert(idKey,value); */

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(n).