371. Patience Piles
A card game deals cards one at a time onto piles. Each card with value v is put on the leftmost pile whose top card is not smaller than v; if no such pile exists, the card starts a new pile on the right. After all cards are dealt, the number of piles equals the length of the longest strictly increasing subsequence of the dealt values.
You are not asked to simulate the piles. Given the array nums of card values in the order they are dealt, return the length of its longest strictly increasing subsequence, where a subsequence keeps the original order but may skip elements. An O(n^2) dynamic program is too slow for two hundred thousand cards; use binary search to get O(n log n).
Example 1
- Input:
- nums = [6,2,8,3,9,4,10]
- Output:
- 4
- Explanation:
One longest strictly increasing subsequence is 2, 3, 4, 10, which has length 4.
Example 2
- Input:
- nums = [7,7,7,7]
- Output:
- 1
- Explanation:
Equal values do not count as increasing, so the answer is 1.
Constraints
1 ≤ nums.length ≤ 2 * 105
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)