Patience Sorting — 以 O(N log N) 求 LIS

nums = [10, 9, 2, 5, 3, 7]

10 -> new pile           | 10 |
 9 -> 10 >= 9, pile 0    | 10 9 |
 2 ->  9 >= 2, pile 0    | 10 9 2 |
 5 ->  2 <  5, new pile  | 10 9 2 | 5 |
 3 ->  5 >= 3, pile 1    | 10 9 2 | 5 3 |
 7 ->  3 <  7, new pile  | 10 9 2 | 5 3 | 7 |

3 piles -> LIS length 3   (e.g. [2, 3, 7])

piles  | 10 9 2 | 5 3 | 7 |
tops   [   2,     3,    7 ]   ==  tails
                                  tails[k] = smallest tail of a run of length k+1

LIS <= piles :  a pile read in DEALING ORDER (bottom -> top) is NON-INCREASING,
                so an increasing subsequence can take at most ONE card from each
                pile -> it cannot be longer than the number of piles

LIS >= piles :  a card on pile k landed there because pile k-1 already had a
                SMALLER top; chain that back pile by pile and you get an actual
                increasing subsequence of length k + 1
                -> the last pile witnesses a run as long as the pile count

# python
# IDEA: patience sorting - tails[k] = smallest tail of an increasing run of
#       length k+1; lower-bound it to find the pile, then extend or overwrite
# time = O(n log n), space = O(n)
def lis_length(nums):
    tails = []

    for num in nums:
        # lower bound : first index with tails[l] >= num
        l, r = 0, len(tails) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if tails[mid] < num:
                l = mid + 1      # NOTE !!! strict < -> an equal tail FAILS this test,
                                 #          so it takes the else and pushes r left
            else:
                r = mid - 1

        if l == len(tails):
            tails.append(num)    # beats every top -> a NEW pile, a longer run exists
        else:
            tails[l] = num       # same length, cheaper tail -> overwrite

    return len(tails)            # NOTE !!! the LENGTH is the answer, not the contents

# python - the same scan, with the library doing the search
# IDEA: bisect_left IS the lower bound written out above
# time = O(n log n), space = O(n)
import bisect

def lis_length_bisect(nums):
    tails = []
    for num in nums:
        l = bisect.bisect_left(tails, num)   # first tail >= num
        if l == len(tails):
            tails.append(num)
        else:
            tails[l] = num
    return len(tails)

// java
// IDEA: same scan on a fixed array - `size` is the pile count, so tails[0..size)
//       is the sorted window the lower bound runs on
// time = O(n log n), space = O(n)
public int lisLength(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;

    for (int num : nums) {
        int l = 0, r = size;
        while (l < r) {                     // lower_bound over tails[0..size)
            int mid = l + (r - l) / 2;
            if (tails[mid] < num) l = mid + 1;
            else r = mid;
        }
        tails[l] = num;                     // overwrite ...
        if (l == size) size++;              // ... or extend, when l lands past the end
    }
    return size;
}

# python - longest NON-DECREASING subsequence
# IDEA: identical scan, bisect_right so an equal value extends instead of replacing
# time = O(n log n), space = O(n)
import bisect

def lnds_length(nums):
    tails = []
    for num in nums:
        l = bisect.bisect_right(tails, num)   # first tail > num
        if l == len(tails):
            tails.append(num)
        else:
            tails[l] = num
    return len(tails)

nums = [2, 2, 2, 3]
bisect_left  -> tails [2, 3]           -> 2   (strictly increasing)
bisect_right -> tails [2, 2, 2, 3]     -> 4   (non-decreasing)

# python
# IDEA: same placement rule, but append to the pile instead of only tracking its top
# time = O(n log n), space = O(n)
import bisect

def patience_piles(nums):
    piles = []       # piles[k] : the cards on pile k, top card LAST
    tops = []        # tops[k] == piles[k][-1], kept flat so bisect can search it

    for num in nums:
        l = bisect.bisect_left(tops, num)
        if l == len(piles):
            piles.append([num])
            tops.append(num)
        else:
            piles[l].append(num)
            tops[l] = num

    return piles     # len(piles) == LIS length; each pile is non-increasing
                     # bottom -> top, i.e. in the order it was dealt

nums  = [3, 4, 5, 1]
tails = [1, 4, 5]      <- 1 sits at index 0 but arrives LAST in the input
len   = 3              <- correct anyway: the LIS is [3, 4, 5]

# python
# IDEA: same scan + two side arrays - the input index of each pile's top, and a
#       parent pointer per element; then walk back from the last pile's top
# time = O(n log n), space = O(n)
import bisect

def lis_reconstruct(nums):
    if not nums:
        return []

    tails = []                    # tail VALUES (the array bisect searches)
    tails_idx = []                # index in nums of each tail
    prev = [-1] * len(nums)

    for i, num in enumerate(nums):
        l = bisect.bisect_left(tails, num)

        # whatever currently ends the run of length l becomes num's predecessor
        if l > 0:
            prev[i] = tails_idx[l - 1]

        if l == len(tails):
            tails.append(num)
            tails_idx.append(i)
        else:
            tails[l] = num
            tails_idx[l] = i

    out = []
    i = tails_idx[-1]             # the top of the last pile ends a longest run
    while i != -1:
        out.append(nums[i])
        i = prev[i]
    return out[::-1]

# python
# IDEA: tails of size <= 2 - first/second ARE tails[0]/tails[1]; the moment a
#       value beats both, a third pile (an increasing triplet) exists
# time = O(n), space = O(1)
class Solution:
    def increasingTriplet(self, nums):
        first = second = float('inf')
        for num in nums:
            if num <= first:
                first = num          # tails[0] = a cheaper length-1 tail
            elif num <= second:
                second = num         # tails[1] = a cheaper length-2 tail
            else:
                return True          # would append tails[2] -> length 3 exists
        return False

# python
# IDEA: non-decreasing variant (bisect_right); the landing index + 1 IS the
#       longest valid course ending at this obstacle
# time = O(n log n), space = O(n)
import bisect

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles):
        tails, ans = [], []
        for h in obstacles:
            i = bisect.bisect_right(tails, h)   # heights may repeat -> bisect_right
            if i == len(tails):
                tails.append(h)
            else:
                tails[i] = h
            ans.append(i + 1)                   # NOTE !!! per-index answer, no extra pass
        return ans

# python
# IDEA: k independent slices arr[r::k]; keep each one's longest NON-DECREASING
#       subsequence (values may repeat) and pay 1 for every element kept out
# time = O(n log n), space = O(n)
import bisect

class Solution:
    def kIncreasing(self, arr, k):
        def lnds(seq):
            tails = []
            for x in seq:
                i = bisect.bisect_right(tails, x)
                if i == len(tails):
                    tails.append(x)
                else:
                    tails[i] = x
            return len(tails)

        return sum(len(arr[r::k]) - lnds(arr[r::k]) for r in range(k))

# python
# IDEA: distinct target -> map arr values to target indices; a common subsequence
#       of (target, arr) is exactly an INCREASING subsequence of the mapped list
# time = O(n log n), space = O(n)
import bisect

class Solution:
    def minOperations(self, target, arr):
        pos = {v: i for i, v in enumerate(target)}   # value -> index in target

        tails = []
        for x in arr:
            if x not in pos:                          # not in target -> unusable
                continue
            p = pos[x]
            i = bisect.bisect_left(tails, p)          # strictly increasing indices
            if i == len(tails):
                tails.append(p)
            else:
                tails[i] = p

        return len(target) - len(tails)               # insert whatever the LIS missed

# python
# IDEA: left[i] = LIS ending at i, right[i] = LIS starting at i (the same scan on
#       the reversed array); a peak needs both sides > 1, so keep the best sum - 1
# time = O(n log n), space = O(n)
import bisect

class Solution:
    def minimumMountainRemovals(self, nums):
        def lis_ending_at_each(seq):
            out, tails = [], []
            for x in seq:
                i = bisect.bisect_left(tails, x)     # strictly increasing
                if i == len(tails):
                    tails.append(x)
                else:
                    tails[i] = x
                out.append(i + 1)
            return out

        left = lis_ending_at_each(nums)
        right = lis_ending_at_each(nums[::-1])[::-1]

        # NOTE !!! a peak cannot be an endpoint -> both sides must exceed 1
        best = max(l + r - 1
                   for l, r in zip(left, right)
                   if l > 1 and r > 1)
        return len(nums) - best