算法笔试模拟题精解之“数组染色”
算法笔试模拟题精解之“数组染色”
贡献者 | 张鹏飞
简介：可以采用链表的思想，定义一个数组 temp 来存放每个递增的子串，题目
需要求出最少的递增子串有多少个，采取的思路是递增的子串越密集越好。
题目描述
等级：中等
知识点：DP、LIS
查看题目：数组染色
codancer 现在有一个长度为 n 的数组 a, 对于每个这个数组的每个数字，我们
必须染上颜色，但是 codancer 有一个限制条件 : 如果 i 输入一个正整数 n 和数组 a。
（1<=n<=100000,0<=a[i]<=1000000000）.
输出最少需要的颜色种类数。
示例 1
输入：
5
[2,1,4,5,3]
输出：
注意
把 a[1],a[3],a[4] 染同一种颜色，把 a[2] 和 a[5] 染成另外一种颜色。
解题思路
大致思路：可以采用链表的思想，定义一个数组 temp 来存放每个递增的子串，题
目需要求出最少的递增子串有多少个，采取的思路是递增的子串越密集越好，即若有
2，4，3，5。那么我最优选择的是密集子串 2，3 和 4，5. 而不是 2，4 和 3，5；即使
对这个测试用例来说，答案都是一样的，但是就题目而言，密集子串是最优的选择。
具体思路：定义一个数组 temp 来存放每个递增的子串，那么我先将第一个元素
放在 temp 数组的第一个位置，从 i=1 开始遍历 x 数组，将 x[i] 与 temp 数组的第一
个元素开始比较（j=0），如果 x[i]>temp[j], 那么我就将 x[i] 元素链接在 temp[j] 元素后
面，又因为这是个数组，不是链表，而且链接后 temp[j] 值再也用不上，和链表的最
后一个元素比较，因此可以直接覆盖 temp[j] 元素，即 temp[j]=x[i]。我说的链接如下
图所示
可以发现，每次比较都是和链表最后一个元素比较，所以前面的元素可以覆盖，
如下面的直接覆盖法，也是用数组实现，很简单。而且还可以发现，temp 数组永远
是递减的，这样也满足密集子串，因为从上往下走，找到满足的即可停止，不需要继
续往下。最终，temp 数组有几个元素，答案就是多少。可以用 ans 一致指向 temp
数组的最后一个元素的位置。
完全理解本解法需要理解我定义的密集子串和链接法转直接覆盖等概念。好好理
解一下，很简单，有什么问题可以在评论区交流。
看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：数组染色
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”