内卷大厂系列最长递增子序列问题五连击

　　一、最长递增子序列I给你一个整数数组nums，找到其中最长严格递增子序列的长度。
　　子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，〔3，6，2，7〕是数组〔0，3，1，6，2，2，7〕的子序列。
　　示例1：输入：nums〔10，9，2，5，3，7，101，18〕输出：4解释：最长递增子序列是〔2，3，7，101〕，因此长度为4。
　　示例2：输入：nums〔0，1，0，3，2，3〕输出：4
　　示例3：输入：nums〔7，7，7，7，7，7，7〕输出：1
　　leetcode1、分析
　　最长递增子序列经典模型题，子序列不一定连续，子串一定连续！
　　方法一：动态规划，定义dp〔i〕含义：必须以i结尾的最长递增子序列是多长，遍历数组，当前来到i位置，往左边找所有小于当前数的最大dp值max（dp〔0i1〕），然后再加个1就是当前最长递增子序列长度，时间复杂度为O（N）
　　方法二：引入ends数组，加入求解左边遍历求解最大dp值的过程，ends〔i〕含义：找到的所有长度为i1的递增子序列中最小结尾是什么，ends数组必须有序（从小到大），时间复杂度为O（NlogN）
　　策略：arr中的任何数，去ends数组有效区中找当前数的最左侧的位置，如果能找到，则更新ends〔i〕cur，然后看这个位置（ends中的i位置）包含自己左侧有几个数就是dp〔i〕中的值，如果在ends中没有找到当前数的最左侧的数，则扩充ends有效区，让ends〔i〕arr〔i〕2、实现2。1、方法一publicstaticintlengthOfLIS（int〔〕arr）｛if（arrnullarr。length0）｛return0；｝int〔〕dpnewint〔arr。length〕；dp〔0〕1；0位置的最长递增子序列长度为1intmaxans1；for（inti1；iarr。i）｛dp〔i〕1；for（intj0；j）｛if（arr〔i〕arr〔j〕）｛0i1位置找所有小于当前数的dp值dp〔i〕Math。max（dp〔i〕，dp〔j〕1）；｝｝maxansMath。max（maxans，dp〔i〕）；更新最大值｝｝2。2、方法二publicstaticintlengthOfLIS（int〔〕arr）｛if（arrnullarr。length0）｛return0；｝int〔〕endsnewint〔arr。length〕；ends〔0〕arr〔0〕；ends〔i〕的含义找到长度为i1的递增子序列中最小结尾是什么，0位置就是长度为011的递增子序列中最小结尾就是数组arr〔0〕位置的数intright0；有效区0。。。right有效，right右边无效intL0；左指针intR0；右指针intM0；中间指针intmax1；for（inti1；iarr。i）｛L0；Rwhile（LR）｛二分查找M（LR）2；if（arr〔i〕ends〔M〕）｛LM1；｝else｛RM1；｝｝Lright1rightMath。max（right，L）；ends〔L〕arr〔i〕；maxMath。max（max，L1）；｝｝二、最长递增子序列II给定一个未排序的整数数组nums，以数组形式返回最长递增子序列，如果有多个最长递增子序列，返回一个即可。
　　注意这个数列必须是严格递增的。
　　示例：输入：〔1，3，5，4，7〕解释：有两个最长递增子序列，分别是〔1，3，4，7〕和〔1，3，5，7〕。1、分析
　　直接用最优解，时间复杂度为O（NlogN），生成最长递增子序列数组2、实现publicstaticint〔〕lis2（int〔〕arr）｛if（arrnullarr。length0）｛｝int〔〕dpgetdp2（arr）；生成最长递增子序列数组dp，每个位置代表当前位置的最长递增子序列长度returngenerateLIS（arr，dp）；生成最长递增子序列｝publicstaticint〔〕getdp2（int〔〕arr）｛int〔〕dpnewint〔arr。length〕；int〔〕endsnewint〔arr。length〕；ends〔0〕arr〔0〕；dp〔0〕1；intright0；有效区0。。。。rightright往右无效intL0；intR0；intM0；for（inti1；iarr。i）｛L0；Rwhile（LR）｛二分查找的过程M（LR）2；if（arr〔i〕ends〔M〕）｛LM1；｝else｛RM1；｝｝Lright1rightMath。max（right，L）；ends〔L〕arr〔i〕；dp〔i〕L1；｝｝publicstaticint〔〕generateLIS（int〔〕arr，int〔〕dp）｛intlen0；最长递增子序列的长度intindex0；最长递增子序列的下标for（inti0；idp。i）｛if（dp〔i〕len）｛lendp〔i〕；｝｝int〔〕lisnewint〔len〕；准备长度为len的递增子序列lis〔len〕arr〔index〕；for（i0；i）｛从后往前推if（arr〔i〕arr〔index〕dp〔i〕dp〔index〕1）｛lis〔len〕arr〔i〕；｝｝｝三、最长递增子序列III每个信封都有长和宽两个维度的数据，A信封如果想套在B信封里面，A信封必须在长和宽上都小于B信封才行。如果给你一批信封，返回最大的嵌套层数。
　　注意：不允许旋转信封。
　　示例1：输入：envelopes〔〔5，4〕，〔6，4〕，〔6，7〕，〔2，3〕〕输出：3解释：最多信封的个数为3，组合为：〔2，3〕〔5，4〕〔6，7〕。
　　示例2：输入：envelopes〔〔1，1〕，〔1，1〕，〔1，1〕〕输出：1
　　leetcode1、分析
　　信封套娃问题（俄罗斯套娃问题）
　　先按照信封的长度从小到大排序，如果长度相同，在按照信封的宽度（高度）从大到小排序
　　把信封的宽度（高度）依次提取出来，求最长递增子序列的长度就是能套几层
　　假如某个信封的宽度为V，因为信封是按照长度从小到大排序的，之前的信封长度必然小于等于当前信封，宽度（高度）又是从大到小排序的，之后的宽度（高度）必然小于等于当前信封，所以这道题的本质就是求按照信封的宽度（高度）最长递增子序列长度是多长，就代表信封能套几层。2、实现publicstaticclassEnvelope｛信封的长度信封的高度publicEnvelope（intweight，intheight）｛｝｝先按照信封的长度从小到大排序，如果长度相等按照信封的高度从大到小排序publicstaticclassEnvelopeComparatorimplementsComparatorEnvelope｛Overridepublicintcompare（Envelopeo1，Envelopeo2）｛returno1。l！o2。l？o1。lo2。l：o2。ho1。h；｝｝publicstaticEnvelope〔〕getSortedEnvelopes（int〔〕〔〕matrix）｛Envelope〔〕resnewEnvelope〔matrix。length〕；for（inti0；imatrix。i）｛res〔i〕newEnvelope（matrix〔i〕〔0〕，matrix〔i〕〔1〕）；｝Arrays。sort（res，newEnvelopeComparator（））；｝publicstaticintmaxEnvelopes（int〔〕〔〕matrix）｛Envelope〔〕envelopesgetSortedEnvelopes（matrix）；int〔〕endsnewint〔matrix。length〕；ends〔0〕envelopes〔0〕。h；intright0；有效区intL0；intR0；intM0；for（inti1；ienvelopes。i）｛L0；Rwhile（LR）｛M（LR）2；if（envelopes〔i〕。hends〔M〕）｛LM1；｝else｛RM1；｝｝Lright1rightMath。max（right，L）；ends〔L〕envelopes〔i〕。h；｝returnright1；｝四、最长递增子序列IV给定一个mxn整数矩阵matrix，找出其中最长递增路径的长度。
　　对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
　　示例1：
　　输入：matrix〔〔9，9，4〕，〔6，6，8〕，〔2，1，1〕〕输出：4解释：最长递增路径为〔1，2，6，9〕。
　　示例2：
　　输入：matrix〔〔3，4，5〕，〔3，2，6〕，〔2，2，1〕〕输出：4解释：最长递增路径是〔3，4，5，6〕。注意不允许在对角线方向上移动。
　　leetcode1、分析
　　矩阵中求最长递增子序列问题，只能上下左右4个方向走动，不能走重复路，对走过的路要标记
　　时间复杂度O（NM），每个位置走一遍，然后上下左右走一遍，即5遍，忽略常数项。2、实现publicstaticintlongestIncreasingPath（int〔〕〔〕matrix）｛intans0；intNmatrix。intMmatrix〔0〕。int〔〕〔〕dpnewint〔N〕〔M〕；增加路径标记，防止重复走路for（inti0；iN；i）｛for（intj0；jM；j）｛每个位置都4个方向走ansMath。max（ans，process（matrix，i，j，dp））；｝｝｝privatestaticintprocess（int〔〕〔〕matrix，inti，intj，int〔〕〔〕dp）｛if（dp〔i〕〔j〕！0）｛说明路走过，直接从dp中拿值returndp〔i〕〔j〕；｝intNmatrix。intMmatrix〔0〕。上intupi0matrix〔i〕〔j〕matrix〔i1〕〔j〕？process（matrix，i1，j，dp）：0；下intdowni（N1）matrix〔i〕〔j〕matrix〔i1〕〔j〕？process（matrix，i1，j，dp）：0；左intleftj0matrix〔i〕〔j〕matrix〔i〕〔j1〕？process（matrix，i，j1，dp）：0；右intrightj（M1）matrix〔i〕〔j〕matrix〔i〕〔j1〕？process（matrix，i，j1，dp）：0；intansMath。max（Math。max（up，down），Math。max（left，right））1；dp〔i〕〔j〕｝五、最长递增子序列V给你一个整数数组nums，判断这个数组中是否存在长度为3的递增子序列。
　　如果存在这样的三元组下标（i，j，k）且满足ijk，使得nums〔i〕nums〔j〕nums〔k〕，返回否则，返回false。
　　示例1：输入：nums〔1，2，3，4，5〕输出：true解释：任何ijk的三元组都满足题意
　　示例2：输入：nums〔5，4，3，2，1〕输出：false解释：不存在满足题意的三元组
　　示例3：输入：nums〔2，1，5，0，4，6〕输出：true解释：三元组（3，4，5）满足题意，因为nums〔3〕0nums〔4〕4nums〔5〕6
　　leetcode1、分析
　　递增的三元子序列，还是最长递增子序列问题。2、实现publicstaticbooleanincreasingTriplet（int〔〕arr）｛if（arrnullarr。length3）｛｝int〔〕endsnewint〔3〕；ends〔0〕arr〔0〕；intright0；有效区intl0；intr0；intm0；for（inti1；iarr。i）｛l0；while（lr）｛m（lr）2；if（arr〔i〕ends〔m〕）｛lm1；｝else｛rm1；｝｝lright1rightMath。max（right，l）；if（right1）｛012｝ends〔l〕arr〔i〕；｝｝
　　小伙伴们有兴趣想了解内容和更多相关学习资料的请点赞收藏评论转发关注我，后面会有很多干货。我有一些面试题、架构、设计类资料可以说是程序员面试必备！所有资料都整理到网盘了，需要的话欢迎下载！私信我回复【000】即可免费获取
　　作者：mzoe666888
　　原文出处：https：mdnice。comwritingfb95914364e3430d916e83976165b974