第一次做困难的题,我感觉想出这种扑克牌求最长递增子序列算法思想的人简直yyds,respect!
一. 题目描述
二. 解法描述(扑克牌法求最长递增子序列)
- 首先用Arrays类的sort方法对这个信封二维数组进行排序,自己定义排序规则的话,要自己实现java.util.Comparator接口,重写compare方法。当o1信封的宽等于o2信封的宽时,如果O2的高度大于O1的高度,则返回正值,则说明O1在O2的前面,如果两者宽度不相等,谁宽小谁在前面。(宽度以升序排列,高度以降序排列,如下图所示)
- 然后就是对高度进行求最长递增子序列的长度。
扑克牌法求最长递增子序列的思想,就是依此从左到右读取扑克牌,每一堆中小的扑克牌才能放到大的扑克牌上面,如果找不到可放置的堆,则新建堆,当遇到有多个堆可以放置时,选择最左的那个堆放置(即求左边界),由图可知,堆的个数就是最长递增子序列的长度。
- piles代表的是堆数,最后最长递增子序列的长度就是堆数大小。top数组上存放的是每一堆上的最上面的那个数字(即当前堆最小的数字),可知top数组是按照从小到大的顺序排列的,poker代表当前要放置的数字,用二分搜索法搜索top数组,使用的是左闭右开的左边界法。如果left=piles,说明poker大于目前top数组中的所有数,则新建堆。最后把poker放入最左边的堆中。
- 动态规划法后续补充~