Leetcode300.最长递增子序列

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
>输入：nums = [10,9,2,5,3,7,101,18]
>输出：4
>解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
>输入：nums = [0,1,0,3,2,3]
>输出：4

示例 3：

1
2
>输入：nums = [7,7,7,7,7,7,7]
>输出：1

使用单调栈和二分查找结合解体

单调栈用来维护一个严格递增的序列，二分查找用于快速定位第一个破坏当前序列递增顶的序列，并且找到后替换以维持栈的单调性

这里主要用到的策略：

  • nums[i] > stack[-1]：栈顶元素比当前元素小，直接放在栈的顶部，是不是不破坏单调栈的单调递增特性
  • nums[i] <= stack[-1]：栈顶元素比当前元素大，这里为了维护单调性，我们要替代栈中比它第一个比它大的元素

参考图：

image-20240902154437452

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def lengthOfLIS(self, nums):
        stack = [nums[0]]
        for i in range(1, len(nums)):
            if nums[i] > stack[-1]:
                # 当前元素大于栈顶元素，则直接添加
                stack.append(nums[i])
            elif nums[i] < stack[-1]:
                # 进行二分查找，找到栈中第一个比当前元素大的元素
                left, right = 0, len(stack) - 1
                while left < right:
                    mid = (left + right) // 2
                    if nums[i] <= stack[mid]:
                        right = mid
                    else:
                        left = mid + 1
                stack[left] = nums[i]

        return len(stack)