首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【手绘漫画】图解LeetCode之最长上升子序列(LeetCode300题),贪心算法 + 二分查找

【手绘漫画】图解LeetCode之最长上升子序列(LeetCode300题),贪心算法 + 二分查找

作者头像
我是管小亮
发布2020-04-20 16:06:00
2890
发布2020-04-20 16:06:00
举报

正文共:1310字 21图

阅读大概需要:4分钟

跟随小博主,每天进步一丢丢

1、前言

手绘漫画系列正式上线!!!"图解LeetCode刷题计划" 来了!!!

今天是第五期,争取每天一期,最多两天一期,欢迎大家监督我。。。公众号监督最好!!!

今日是贪心算法,还有好吃的~

2、题目

首先看一下题目,

应该第一时间先想到贪心算法,为什么呢?

如果要使上升子序列尽可能的长,那么就要让序列上升得尽可能慢(最好一次只变化1)。

因为我算法还没学完。。。动态规划还没学。。。这一期就来长长见识吧!

大写的惨字!

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。

3、正文

首先分析一下情况,

这里最重要的是一个思想,即贪心算法——考虑如果要使上升子序列尽可能的长,则要让序列上升尽可能的慢,所以需要一个数组来记录,也就是 d

遍历整个数组,寻找上升子序列,只要下一个元素大于上一个元素,就先读入,然后与 d 中保存的最长上升子序列的末尾元素的最小值比较,如果能满足贪心算法,就录入,以此类推。

这里让人拍手叫绝的一个点就是——3,不知道你看出来为啥了嘛?

复杂度:

  • 时间复杂度:。数组 长度 n,二分搜索是 。
  • 空间复杂度:,长度为 n 的数组 d

4、代码

int lengthOfLIS(int* nums, int numsSize){
    int len = 1;
    if (numsSize == 0) return 0;
    int d[numsSize+1];
    d[len] = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] > d[len]){
         d[++len] = nums[i];
        }
        else{
            int l = 1, r = len, pos = 0; 
            while (l <= r) {
                int mid = l + (r - l)/2;
                if (d[mid] < nums[i]) {
                    pos = mid;
                    l = mid + 1;
                }
                else {
                 r = mid - 1;
                }
            }
            d[pos + 1] = nums[i];
        }
    }
    return len;
}

5、讨论

1、严格意义上,这个题和二分查找没啥特别大的关系,23333。

一起来看一个实例分析吧:

2、为什么数组 d 要是 d[numsSize+1]?

原因很简单,为了保证下标同步。

3、数组 d 是单调递增的嘛?

看了LeetCode上的题解,感觉反证不如直接得来的快,d 其实就是我们需要的最长子序列,因为是上升的,自然得是递增的。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-04-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员管小亮 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档