子串/子序列最值

Subarray最值简介

注意区分：子串/subarray是一个序列的连续子序列，而子序列/subsequnce不一定需要连续。

在原有数组（或字符串）中寻找子串（或子字符串）的最值，暴力法一般是 O(n³)的时间复杂度。因为枚举首尾需要O(n²)，而判断断子串符合要求另需要O(n)。

要把总时间复杂度O(n³)降下来到有O(n²)，O(nlogn)甚至O(n)，有这么几种方法可以加速：

前缀和
双指针（滑动窗口）
动态规划
二分查找
中心扩展
单调栈

(1) 前缀和

用数组或者哈希表来记录前 $i$ 个数字的连续和。

参考模版：

presum = [0 for _ in range(len(n)+1)] # sum of nums[:i]
for i in range(n):
    presum[i+1] = presum[i] + nums[i]

前缀和可以用来加速求解区间和。定义前缀和 $S_i = \sum n_{0, 1, ..., i-1}$ ，那么

$\sum n_{i...j} = s_{j+1} - s_{i}$ 。

给定一个二进制数组 nums , 
找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。


输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

def findMaxLength(nums):
    res = 0
    m = {0: -1}
    cnt = 0
    for i, n in enumerate(nums):
        cnt += 1 if n==0 else -1
        if cnt in m:
            res = max(res, i-m[cnt])
        else:
            m[cnt] = i
    return res

给你一个整数数组 nums 和一个整数 k ，
编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

def checkSubarraySum(nums, k):
    k = abs(k)
    m = {0: -1}
    s = 0
    for i, n in enumerate(nums):
        s += n
        s = s%k
        if s in m:
            if i-m[s] > 1:
                return True
        else:
            m[s] = i
    return False

(2) 双指针

参考模版：

left = right = 0
window = defaultdict(int)
while right < len(s):
    a = s[right]
    right += 1
    window[a] += 1
    
    while (window[c]...): # check condition
        b = s[left]
        left += 1
        window[d] -= 1
    res = ... # here window contains s[left, right+1]
              # with substring lenGth right-left

这个方法很实用于解决这样一类问题：符合某某要求的最长子串。有一些题目看上去不像子串最值，但是通过转换就变成了““题，可以用滑动窗口求解。

很重要的一点就是：如何定义"符合要求"。下面几个例子感受一下：

简单：

无重复字符的最长子串 [LC3]: 要求=子串无重复字符
最小覆盖子串 [LC76]: 要求=子串含有所有target元素
长度最小的子数组 [LC209]: 要求=子串和≥target
至多包含K个不同字符的最长子串 [LC340]: 要求=子串最多包含K个不同字符

中等：

找到字符串中所有字母异位词 [LC438]: 要求=子串是target的anagram
尽可能使字符串相等 [LC1208]: 要求=子串cost的和≤budget
最高频元素的频数 [LC5739]: 首先排序，要求=（最大元素x子串长度 - 子串和）≤budget

(3) 动态规划

情况一：一次遍历，用O(1)的空间就能解决。相当于运用了滚动数组的动态规划，因为转移方程中f[i]只依赖于f[i-1]例子有：

最长连续递增序列 [LC674]
最大子序和 [LC53] (延伸：线段树）

情况二：二维DP或区间DP。具体参见动态规划章节。

(4) 二分查找

对“符合某某要求的xx最大值子串“，二分查找的思路一般是通过猜xx最大值->验证可行性->修正的过程。是二分查找中比较难的类型。有的时候要借助于前缀和来帮助快算区间和。

(5) 中心扩展/单调栈

柱状图中最大的矩形

参考代码：

分治：从中间向外贪心展开，左右分别操作，最后合并结果。虽然能得到正确答案，然而时间复杂度为O(nlogn)。

def largestFromPoint(heights, m):
    if not heights: return 0
    height, width = heights[m], 1

    res = height
    l, r = m-1, m+1
    while l>=0 or r<len(heights):
        width += 1
        left = heights[l] if l>=0 else float('-inf')
        right = heights[r] if r<len(heights) else float('-inf')
        if left>right:
            l -= 1
        else:
            r += 1
        height = min(height, max(left, right))
        res = max(res, height * width)
    return res

def largestRectangleArea(heights):
    if not heights: return 0
    mid = len(heights) // 2
    me =  self.largestFromPoint(heights, mid)
    left = self.largestRectangleArea(heights[:mid])
    right = self.largestRectangleArea(heights[mid+1:])
    return max(me, left, right)

为了寻求O(n)的算法，我们再观察能发现，包含每个点的最大柱形面积为

$\text{height}*\text{width} \\ = \text{my height} * (\text{next shorter ind} - \text{previous shorter ind} -1)$

利用递增单调栈，next shorter index就能通过模版找到。因为是递增栈，所以previous shorter index就是栈中前一个元素（也就是我弹出后剩下的栈顶）。为了防止栈顶没有了元素，我们防御性编程地一开始在数组头尾增加了0。

def largestRectangleArea(heights):
    res = 0
    stack = []
    for i, h in enumerate([0]+heights+[0]):
        while stack and h<stack[-1][1]:
            ind, height = stack.pop()
            res = max(res, (i-stack[-1][0]-1)*height)
        stack.append((i, h))
    return res

Subsequence最值

枚举长度为n的序列的所有Subsequence有2ⁿ个，所以枚举肯定会超时。subsequence的最值一般通过O(n²)的动态规划求解。

最长递增子序列（LIS）: 有O(nlogn)的二分解法
最大整除子集（LDS）: 这题本质和LIS一样，源自于%关系的递推性。
LIS中 $a > b, b>c \Rightarrow c>a$ ，类似的 $a \% b = 0, c\%b=0 \Rightarrow c\%a=0$ 。所以在两题中，如果[a,b]是一个答案的话，[a,b,c]是一个更好的答案。
最长公共子序列（LCS）
最长递增子序列的个数 [LC673]
最长等差数列 [LC1027]
等差数列划分 II - 子序列 [LC446]

# DP: O(N^2)
def lengthOfLIS(nums):
    f = [1 for _ in range(len(nums))]
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                f[i] = max(f[i], f[j] + 1)
    return max(f)
    
# 二分查找O(NlogN)解法
def lengthOfLIS(nums):
    f = [float('inf') for _ in range(len(nums))]
    for n in nums:
        f[bisect.bisect_left(f, n)] = n
    return bisect.bisect_left(f, float('inf'))

def largestDivisibleSubset(nums):
    nums.sort()
    f = [[x] for x in nums] # answer at nums[i]
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[j]%nums[i]==0 and len(f[i])+1 > len(f[j]):
                f[j] = f[i] + [nums[j]]
    return max(f, key=len)

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    f = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1]==text2[j-1]:
                f[i][j] = f[i-1][j-1]+1
            else:
                f[i][j] = max(f[i][j-1], f[i-1][j])
    return f[-1][-1]

Previous时间复杂度必知 Next贪心与动态规划

Last updated 4 years ago

Was this helpful?