日拱两卒（二）

90#

给一个括号序列，问最长的一串合法括号。

合法的一串括号一定是连续的，而且每个右括号一定是和最近的左括号配对。

拿栈存左括号，先扫一遍把所有配对的左右括号标记，再扫一遍找最长的一串标记。

1
class Solution:
2
    def longestValidParentheses(self, s: str) -> int:
3
        stack = []
4
        n = len(s)
5
        v = [False] * n
6

7
        for i in range(n):
8
            if s[i] == '(':
9
                stack.append(i)
10
            elif s[i] == ')' and len(stack):
11
                left = stack.pop()
12
                v[left] = v[i] = True
13

14
        ans, cnt, i = 0, 0, 0
15
        while i < n:
16
            if v[i]:
17
                cnt += 1
18
                ans = max(ans, cnt)
19
            else:
20
                cnt = 0
21
            i += 1
22

23
        return ans

89#

能否把一个数组里的数字分成两个集合，每个集合的和相等。

先判奇偶。

问题变成能否从n个数里选某些数使得和为m，是背包问题。

1
class Solution:
2
    def canPartition(self, nums: List[int]) -> bool:
3
        s = sum(nums)
4
        if s & 1:
5
            return False
6

7
        n = len(nums)
8

9
        @cache
10
        def dfs(i, j) -> bool:
11
            if i == 0:
12
                return j == 0 or j == nums[0]
13
            if j < 0:
14
                return False
15
            return dfs(i - 1, j) or dfs(i - 1, j - nums[i])
16

17
        return dfs(n - 1, s / 2)

88#

乘积最大子数组。

因为这个数组里有负数，所以要同时维护只考虑前i个数且取第i个数的最大值和最小值，可能负负得正。

1
class Solution:
2
    def maxProduct(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        f = [float('-inf')] * n
5
        g = [float('inf')] * n
6

7
        f[0] = nums[0]
8
        g[0] = nums[0]
9
        for i in range(1, n):
10
            f[i] = max(f[i - 1] * nums[i], g[i - 1] * nums[i], nums[i], f[i])
11
            g[i] = min(g[i - 1] * nums[i], f[i - 1] * nums[i], nums[i], g[i])
12

13
        return max(f)

87#

最长上升子序列。

最重要的是理解O(nlogn)做法的思想。

先看代码实际意味着做的事情。

想象数组是一副扑克牌，现在按以下规则分成若干堆牌堆：

为当前牌找到第一个牌堆顶部牌大于等于它的堆，放上去。

如果没找到，就以这个牌新开一个堆。

最后牌堆的数量就是LIS长度。

为什么两者等价呢？

每个牌堆，都精确对应了一个“某个长度的上升子序列”的最好结尾。

第k个牌堆顶部的牌，是目前为止，能构成"长度为k的LIS"的最小可能结尾数字。

具体例子，考虑[3, 1, 5]。

新建第一个堆，堆顶是3，意味着想构成长度为1的子序列，末尾最小可以是3。
1 < 3，想构成长度为1的子序列，末尾最小可以是1。1比3更有潜力。
5比前两个数都大，无法去优化长度为1的子序列的末尾，但它带来了长度为2的子序列的想象空间，新开一个堆。

核心比喻抗遗忘：转化分牌堆，维护一个有“潜力”的结构。

1
class Solution:
2
    def lengthOfLIS(self, nums: List[int]) -> int:
3
        d = []
4
        n = len(nums)
5

6
        for num in nums:
7
            l, r = 0, len(d)
8
            while l < r:
9
                mid = (l + r) >> 1;
10
                if num <= d[mid]:
11
                    r = mid
12
                else:
13
                    l = mid + 1
14

15
            if l < len(d):
16
                d[l] = num
17
            else:
18
                d.append(num)
19

20
        return len(d)