LeetCode-354-俄罗斯套娃问题

第一次做困难的题,我感觉想出这种扑克牌求最长递增子序列算法思想的人简直yyds,respect!

一. 题目描述

LeetCode-354-俄罗斯套娃问题

二. 解法描述(扑克牌法求最长递增子序列)

LeetCode-354-俄罗斯套娃问题

  1. 首先用Arrays类的sort方法对这个信封二维数组进行排序,自己定义排序规则的话,要自己实现java.util.Comparator接口,重写compare方法。当o1信封的宽等于o2信封的宽时,如果O2的高度大于O1的高度,则返回正值,则说明O1在O2的前面,如果两者宽度不相等,谁宽小谁在前面。(宽度以升序排列,高度以降序排列,如下图所示)
    LeetCode-354-俄罗斯套娃问题
  2. 然后就是对高度进行求最长递增子序列的长度。
    LeetCode-354-俄罗斯套娃问题
    扑克牌法求最长递增子序列的思想,就是依此从左到右读取扑克牌,每一堆中小的扑克牌才能放到大的扑克牌上面,如果找不到可放置的堆,则新建堆,当遇到有多个堆可以放置时,选择最左的那个堆放置(即求左边界),由图可知,堆的个数就是最长递增子序列的长度。
    LeetCode-354-俄罗斯套娃问题
  3. piles代表的是堆数,最后最长递增子序列的长度就是堆数大小。top数组上存放的是每一堆上的最上面的那个数字(即当前堆最小的数字),可知top数组是按照从小到大的顺序排列的,poker代表当前要放置的数字,用二分搜索法搜索top数组,使用的是左闭右开的左边界法。如果left=piles,说明poker大于目前top数组中的所有数,则新建堆。最后把poker放入最左边的堆中。
  4. 动态规划法后续补充~
上一篇:LeetCode 397 整数替换[递归] HERODING的LeetCode之路


下一篇:P1001 A+B Problem