解题思路

  1. 先对height升序排序,同height的weight降序排序(利用zip组合列表后排序);
  2. 问题转为化为求weight的最长上升子序列(Longest Increasing Subsequence, LIS);

代码

class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        if len(height) ==1:
            return 1
        hw = list(zip(height, weight))
        hw.sort(key=lambda x:[x[0],-x[1]])
        # hw = [i[1] for i in hw]
        _,hw = zip(*hw)

        dp = [hw[0]]
        for i in range(1,len(hw)):
            is_replace = False
            for j in range(len(dp)):
                if dp[j] >= hw[i]:
                    dp[j] = hw[i]
                    is_replace = True
                    break
            if not is_replace:
                dp.append(hw[i])

        return len(dp)

参考

讲的很好
https://leetcode-cn.com/problems/circus-tower-lcci/solution/c-onlogn-by-lzn27/
动态规划(DP)
https://www.zhihu.com/question/23995189

最后修改日期: 2020年4月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。