单调不减序列查询第一个大于等于_【算法打卡】将数组拆分成斐波那契序列
难度：中等
题目：
给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上，斐波那契式序列是一个非负整数列表 F，且满足：
0 <= F[i] <= 2^31 - 1，(也就是说，每个整数都符合 32 位有符号整数类型)；F.length >= 3；对于所有的
0 <= i < F.length - 2，都有F[i] + F[i+1] = F[i+2]成立。
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
-------------------------------------------------------
思考：
数组分割成斐波那契序列。
我们都知道，斐波那契序列是a[i]中，a[i-2]+a[i-1]=a[i]，任意三个连续的数，前两项和等于第三项。
以前大学都写过斐波那契序列的，直接就是一个递归，
更甚者，硬编码的，
号称史上最快算斐波那契数的，时间空间都是O(1)。
那能不能直接写把斐波那契数拿去匹配呢，不在这30个斐波那契数的就直接返回false。
答案就是不行。满脑子都是偷鸡。
因为题目都说了，数字不能以 0 开头，而且示例也有说，那不是正经的斐波那契序列，而是用他的计算方式。而且不定长度，有可能11,0,11这种，也算。
固然只能实在的。
那可以来个硬编码。俗称暴力，民间流传为不讲码德。
从第一个数1位，第二个数1位，第三个数 1 位开始，如果满足a[i-2]+a[i-1]=a[i]，就向后移动三位。
否则就是第一个数1位，第二个数1位，第三个数 2 位开始，
。
。
第一个数 2 位，第二个数1位，第三个数 1 位开始，如果满足a[i-2]+a[i-1]=a[i]，就向后移动三位。
。
。
(十年之后)
直到刚好取到字符串最后一位而且满足a[i-2]+a[i-1]=a[i]。那就是成立。
否则false。
看起来很蠢。
可以这样做，但是确实有点蠢，因为太多不必要操作。
例如：
第一个数1位，第二个数1位，第三个数 2 位开始。如果最后那个数两位都不满足就没必要向后加了。
还有就是，第一个数 2 位，第二个数1位，第三个数 1 位开始，那是必然不成立的，因为第一个都比第三个数大了。
所以肯定还有优化空间的。
这时候回溯法就不请自来了。
回溯法概念：
回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
嗦白蜡，就是，
例如上面的例子中，第一个数1位，第二个数1位，判断完第三个数 2 位不成立后，就不再去判断第三个数三位的情况了，直接返回到第二位取两位，然后继续第三位的操作。
当第二位超出了一定大小例如Integer.MAX_VALUE，后也不再判断后面位数，跳回到第一位，第一位取两位，然后再往后走。
简单如图：(示例1)
这个方法在经典的8皇后问题中特别经典，反正就是经典。
递归代码实现：
public ListsplitIntoFibonacci(String S) { List res = new ArrayList<>(); backtrack(S.toCharArray(), res, 0); return res;}public boolean backtrack(char[] digit, List res, int index) {//边界条件判断，如果截取完了，并且res长度大于等于3，表示找到了一个组合。 if (index == digit.length && res.size() >= 3) return true; for (int i = index; i < digit.length; i++) {//两位以上的数字不能以0开头 if (digit[index] == '0' && i > index) break;//截取字符串转化为数字 long num = subDigit(digit, index, i + 1);//如果截取的数字大于int的最大值，则终止截取 if (num > Integer.MAX_VALUE) break; int size = res.size();//如果截取的数字大于res中前两个数字的和，说明这次截取的太大，直接终止，因为后面越截取越大 if (size >= 2 && num > res.get(size - 1) + res.get(size - 2)) break; if (size <= 1 || num == res.get(size - 1) + res.get(size - 2)) {//把数字num添加到集合res中 res.add((int) num);//如果找到了就直接返回 if (backtrack(digit, res, i + 1)) return true;//如果没找到，就会走回溯这一步，然后把上一步添加到集合res中的数字给移除掉 res.remove(res.size() - 1); } } return false;}//相当于截取字符串S中的子串然后转换为十进制数字private long subDigit(char[] digit, int start, int end) { long res = 0; for (int i = start; i < end; i++) res = res * 10 + digit[i] - '0'; return res;}时间复杂度：最坏情况，O(n!)
空间复杂度：O(n)
----------------------------------完--------------------------------
objection