leetcode300：最长递增子序列

题目链接

leetcode

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

/*
    状态表示：
        f[i] 表示以 nums[i] 这个数结尾的递增子序列的长度，取 max。
    状态计算：
        f[i] = max(f[j] + 1)，a[j] < a[i]，其中 j = 1, 2, ..., i - 1

    时间复杂度：O(n^2)
        状态数 * 转移数 = O(n*n) = O(n^2)
    空间复杂度：O(n)
        数组需要 O(n) 的空间。
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1);
        int res = 0;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < i; j ++) {
                if (nums[i] > nums[j]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            res = max(res, f[i]);
        }

        return res;
    }
};

/*
    贪心 + 二分查找
    贪心，如果使上升子序列尽可能的长，则需要让序列上升得尽可能慢。
    因此，希望每次在上升子序列最后加的那个数尽可能小。

    基于上面的贪心思路：
        维护数组 f[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值，
        len 表示当前最长上升子序列的长度。
    初始化：
        len = 1，f[1] = nums[0]
    依次遍历数组 nums 中的每个元素，并更新数组 f 和 len 的值。
        若 nums[i] > f[len]，则更新 len = len + 1；
        否则，找到小于 nums[i] 的最后一个元素的下标 r，并更新 f[r + 1] = nums[i]。
    根据 f 数组的单调性，二分查找寻找下标 i，优化时间复杂度。

    时间复杂度：O(nlogn)
        数组 nums 的长度为 n，更新 f 数组时二分搜索需要 O(logn)，
        所以总时间复杂度为 O(nlogn)。
    空间复杂度：O(n)
        额外数组长度为 n。
*/
class Solution_2 {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), length = 1;
        vector<int> f(n + 1, 0);
        f[length] = nums[0];
        for (int i = 1; i < n; i ++) {
            if (nums[i] > f[length]) {
                f[++ length] = nums[i];
            } else {
                // f[1...len] 中找到小于 nums[i] 的最后一个元素的下标 r
                // 若找不到，则说明所有的数都比 nums[i] 大，更新 f
                int l = 0, r = length - 1;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (f[mid] < nums[i]) l = mid;
                    else r = mid - 1;
                }
                f[r + 1] = nums[i];
                length = max(length, r + 1);
            }
        }

        return length;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_cases = {
        {10,9,2,5,3,7,101,18},
        {0,1,0,3,2,3},
        {7,7,7,7,7,7,7}
    };

    for (auto& nums : test_cases) {
        cout << "Input: ";
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
        cout << "Output: " << solution.lengthOfLIS(nums) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   动态规划：
       使用一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
       初始化 dp 数组，每个元素的初始值为 1（每个元素自身可以构成长度为 1 的子序列）。
       遍历每个元素 nums[i]，对于每个 i，再遍历所有 j < i，
       如果 nums[i] > nums[j]，则更新 dp[i] 为 max(dp[i], dp[j] + 1)。

   时间复杂度：O(n^2)
       由于使用了两层循环，时间复杂度为 O(n^2)。
   空间复杂度：O(n)
       使用了一个大小为 n 的数组 dp，空间复杂度为 O(n)。
*/
// lengthOfLIS 返回最长递增子序列的长度
func lengthOfLIS(nums []int) int {
    n := len(nums)
	if n == 0 {
		return 0
	}

	// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
	dp := make([]int, n)
	for i := range dp {
		dp[i] = 1 // 每个元素至少可以构成长度为 1 的子序列
	}

	// 遍历每个元素
	for i := 1; i < n; i ++ {
		for j := 0; j < i; j ++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
	}

	// 找到 dp 中的最大值
	maxLength := 0
	for _, length := range dp {
		maxLength = max(maxLength, length)
	}

	return maxLength
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected int
	}{
		{
			nums:    []int{10, 9, 2, 5, 3, 7, 101, 18},
			expected: 4,
		},
		{
			nums:    []int{0, 1, 0, 3, 2, 3},
			expected: 4,
		},
		{
			nums:    []int{7, 7, 7, 7, 7, 7, 7},
			expected: 1,
		},
	}

	for i, tc := range testCases {
		result := lengthOfLIS(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}