@ninijia 在 Leetcode每日一题练习 ------ 2601. 质数减法运算 中发帖
从Leetcode 每日一题练习继续讨论:
2601. 质数减法运算
2601. Prime Subtraction Operation
题解
注意题目nums[i]的取值范围在1~1000之间,数字范围不大,则可先用筛法求出该范围内的所有素数备用。这里使用线性筛法。
考虑本题中要求最终得到的是严格递增的数组,则需要求出最后一部分符合严格递增的子数组的起始位置,对于末尾的这部分符合严格递增的子数组不需要做任何改动,因为本题中只能将数字减小,不能变大,而对这段严格递增子数组的起始数字,如果将其变得更小,则前面的数字可调整的范围就会变得更小,就不一定能够构造出符合题目要求的数组。
在找到起始位置后,设该位置的数字为p,对在该位置之前的子数组,可从头遍历并使用贪心算法结合二分搜索,贪心是指每次都将数字变得尽可能小,假设下标为k的数字为n,遍历到下标k+1时数字应该大于n,假设k+1处的...