673. Number of Longest Increasing Subsequence

Medium

Description

給定一個未排序的整數陣列 nums，回傳最長嚴格遞增子序列的個數。

Example:

Input: nums = [1,3,5,4,7] Output: 2

Intuition#

在 LIS 的 DP 基礎上，額外維護一個計數陣列來追蹤每個長度有多少種方式達成。

len[i] = 以 nums[i] 結尾的最長遞增子序列長度
cnt[i] = 以 nums[i] 結尾的最長遞增子序列個數
當找到更長的 LIS 時重置計數，長度相等時累加計數

Approaches#

1: DP O(n^2)#

概念: 對每個元素掃描前面所有比它小的元素，維護長度和計數
時間複雜度: O(n^2)
空間複雜度: O(n)

class Solution {
    fun findNumberOfLIS(nums: IntArray): Int {
        val n = nums.size
        val len = IntArray(n) { 1 }
        val cnt = IntArray(n) { 1 }
        var maxLen = 1
        for (i in 1 until n) {
            for (j in 0 until i) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1
                        cnt[i] = cnt[j]
                    } else if (len[j] + 1 == len[i]) {
                        cnt[i] += cnt[j]
                    }
                }
            }
            maxLen = maxOf(maxLen, len[i])
        }
        var result = 0
        for (i in 0 until n) {
            if (len[i] == maxLen) result += cnt[i]
        }
        return result
    }
}

⭐2: Segment Tree (Optimal)#

概念: 用線段樹在值域上維護 (最長長度, 計數) 對，支援快速查詢和更新
時間複雜度: O(n log n)
空間複雜度: O(n)

class Solution {
    fun findNumberOfLIS(nums: IntArray): Int {
        // 座標壓縮
        val sorted = nums.toSortedSet().toList()
        val rank = HashMap<Int, Int>()
        sorted.forEachIndexed { i, v -> rank[v] = i + 1 }
        val m = sorted.size

        // 線段樹：每個節點存 (maxLen, count)
        val treeLen = IntArray(4 * m)
        val treeCnt = IntArray(4 * m)

        fun merge(len1: Int, cnt1: Int, len2: Int, cnt2: Int): Pair<Int, Int> {
            if (len1 > len2) return len1 to cnt1
            if (len2 > len1) return len2 to cnt2
            return len1 to (cnt1 + cnt2)
        }

        fun query(node: Int, s: Int, e: Int, l: Int, r: Int): Pair<Int, Int> {
            if (r < s || e < l) return 0 to 0
            if (l <= s && e <= r) return treeLen[node] to treeCnt[node]
            val mid = (s + e) / 2
            val left = query(2 * node, s, mid, l, r)
            val right = query(2 * node + 1, mid + 1, e, l, r)
            return merge(left.first, left.second, right.first, right.second)
        }

        fun update(node: Int, s: Int, e: Int, pos: Int, len: Int, cnt: Int) {
            if (s == e) {
                val (ml, mc) = merge(treeLen[node], treeCnt[node], len, cnt)
                treeLen[node] = ml
                treeCnt[node] = mc
                return
            }
            val mid = (s + e) / 2
            if (pos <= mid) update(2 * node, s, mid, pos, len, cnt)
            else update(2 * node + 1, mid + 1, e, pos, len, cnt)
            val (ml, mc) = merge(treeLen[2 * node], treeCnt[2 * node], treeLen[2 * node + 1], treeCnt[2 * node + 1])
            treeLen[node] = ml
            treeCnt[node] = mc
        }

        var maxLen = 0
        var ans = 0
        for (num in nums) {
            val r = rank[num]!!
            val (prevLen, prevCnt) = if (r > 1) query(1, 1, m, 1, r - 1) else 0 to 0
            val curLen = prevLen + 1
            val curCnt = if (prevCnt == 0) 1 else prevCnt
            update(1, 1, m, r, curLen, curCnt)
            if (curLen > maxLen) { maxLen = curLen; ans = curCnt }
            else if (curLen == maxLen) ans += curCnt
        }
        return ans
    }
}

🔑 Takeaways#

Pattern: LIS 計數 — 在標準 LIS DP 上增加計數維度
關鍵技巧: 當新的長度等於已知最長時，累加計數而非重置；O(n^2) 解法在面試中通常已足夠