标签搜索

目 录CONTENT

文章目录

最长上升子序列.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 13 阅读 / 2,310 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

最长上升子序列

@[toc]

一、问题描述

 给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

方法一:动态规划

  • 类似的, 我们设计动态规划算法, 不是需要⼀个 dp 数组吗? 我们可以假设dp[0...i-1]都已经被算出来了,
  • 然后问⾃⼰: 怎么通过这些结果算出dp[i]?
  • ⾸先要定义清楚dp 数组的含义, 即 dp[i] 的值到底代表着什么?我们的定义是这样的: dp[i] 表⽰以 nums[i] 这个数结尾的最⻓递增⼦序列的⻓度。
  • 例如
    在这里插入图片描述

在这里插入图片描述
根据这个定义, 我们的最终结果(⼦序列的最⼤⻓度) 应该是 dp 数组中的最⼤值。

int res = 0;
for (int i = 0; i < dp.size(); i++) {
	res = Math.max(res, dp[i]);
}
 return res;

我们已经知道了 $dp[0...4]$ 的所有结果, 我们如何通过这些已知结果推出$dp[5]$ 呢?
在这里插入图片描述

  • 根据刚才我们对 dp 数组的定义, 现在想求 dp[5] 的值, 也就是想求以 nums[5] 为结尾的最⻓递增⼦序列。
  • nums[5] = 3, 既然是递增⼦序列, 我们只要找到前⾯那些结尾⽐ 3 ⼩的⼦序列, 然后把 3 接到最后, 就可以形成⼀个新的递增⼦序列, ⽽且这个新的⼦序列⻓度加⼀。
  • 当然, 可能形成很多种新的⼦序列, 但是我们只要最⻓的, 把最⻓⼦序列的⻓度作为 dp[5] 的值即可
for (int i = 0; i < nums.length; i++) {
	for (int j = 0; j < i; j++) {
		if (nums[i] > nums[j])
			dp[i] = Math.max(dp[i], dp[j] + 1);
	}
}

完整代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty())
        {
            return 0;
        }

        vector<int> dp(nums.size(),1);//定义一个数组;dp[i]:代表以nums[i]为结尾的元素的最长递增序列,因为每个元素自身都是一个递增序列,所以初始化为1
        //外层遍历:每次取nums中的每个元素作为最后一个递增序列
        for(int i = 0;i < nums.size();i++)
        {
            //内层遍历:每次从0到 i - 1 中取数和nums[i]进行比较,
            for(int j = 0;j < i;j++)
            {
                //如果nums[i] > nums[j] 代表可以和前面的元素构成一个递增序列,因为以nums[i]结尾的递增序列不只有一个,选取最大的一个
                if(nums[i] > nums[j])
                {
                    dp[i] = max(dp[i],dp[j] + 1);
                }
            }
        }

        //遍历dp数组,找到以nums中所有元素作为结尾最大值返回
        int Max = INT_MIN;
        for(auto e : dp)
        {
            Max = e > Max ? e : Max;
        }
        return Max;
    }
};

方法二:⼆分查找

  • 这个解法的时间复杂度会将为 O(NlogN), 但是说实话, 正常⼈基本想不到这种解法(也许玩过某些纸牌游戏的⼈可以想出来) 。
  • 所以如果⼤家了解⼀下就好, 正常情况下能够给出动态规划解法就已经很不错了。
  • 根据题⽬的意思, 我都很难想象这个问题竟然能和⼆分查找扯上关系。 其实最⻓递增⼦序列和⼀种叫做 patience game 的纸牌游戏有关, 甚⾄有⼀种排序⽅法就叫做 patience sorting(耐⼼排序)。
  • 为了简单期间, 后⽂跳过所有数学证明, 通过⼀个简化的例⼦来理解⼀下思路。
  • ⾸先, 给你⼀排扑克牌, 我们像遍历数组那样从左到右⼀张⼀张处理这些扑克牌, 最终要把这些牌分成若⼲堆
    在这里插入图片描述
    处理这些扑克牌要遵循以下规则:
    **只能把点数⼩的牌压到点数⽐它⼤的牌上。 如果当前牌点数较⼤没有可以放置的堆, 则新建⼀个堆, 把这张牌放进去。==如果当前牌有多个堆可供选择,则选择最左边的堆放置(为保证有序,这种做法非常有效)== **⽐如说上述的扑克牌最终会被分成这样 5 堆(我们认为 A 的值是最⼤的,⽽不是 1)
    在这里插入图片描述
    在这里插入图片描述
    按照上述规则执⾏, 可以算出最⻓递增⼦序列, 牌的堆数就是最⻓递增⼦序列的⻓度, 证明略
    在这里插入图片描述
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int* top = new int[nums.size()];

        // 牌堆数初始化为 0
        int piles = 0;

        //遍历nums中的每一个元素
        for (int i = 0; i < nums.size(); i++) 
        {
            // 要处理的扑克牌,保存一下
            int poker = nums[i];

            /***** 搜索左侧边界的⼆分查找 *****/
            int left = 0;
            int right = piles;
            while (left < right) 
            {
                int mid = (left + right) / 2;
                if (top[mid] > poker)
                {
                    right = mid;
                } 
                else if (top[mid] < poker) 
                {
                    left = mid + 1;
                } 
                else 
                {
                    right = mid;
                }
            } 
            /*********************************/
            // 没找到合适的牌堆, 新建⼀堆
            if (left == piles) 
                piles++;

            // 把这张牌放到牌堆顶
            top[left] = poker;
        } 
        // 牌堆数就是 最长递增序列 ⻓度
        return piles;

    }
};

不明白代码中的二分法请点击
二分法详解

0

评论区