解题思路

给定一个满足“循环非递增”（准确地说：循环非递减）规律的数组 boards，它等价于一个非递减有序数组的某个旋转。在这样的环形序列中，只有在“最大值 → 最小值”的连接处会出现一次下降，其余相邻位置都满足不下降。

要把新木板长度 x 插入到合适位置并保持这一性质，同时当可插位置不唯一时取最小下标。可用经典的“循环有序表插入（类似 LeetCode 708）”判定规则在线性扫描中完成：

设考察在位置 i 前插入（即夹在 prev=boards[(i-1+n)%n] 与 curr=boards[i] 之间）：

1. 普通段（不跨越断点）：若 prev <= curr，则当 prev <= x <= curr 时可以插入到 i。

题目内容

海蒂爷爷想做一个奇怪的木桶。

他去山里砍了一些木柴加工成高矮不一的木板，然后他把木板按高矮排好顺序，依次取出，竖在地上，排列成一个圆桶状。该圆桶满足循环单调非递减规律(即从第 $1$ 块木板开始，后续的木板不矮于前一根，直到最高的木板与第一块最矮的木板连接在一起)。比如 $[3$ $4$ $5$ $5$ $1$ $2$ $2]$ ，表示有 $7$ 根木板，最矮的木板高度为 $1$ ，最高的木板高度为 $5$ 。起始木板高度为 $3$ ，然后按木板高度依次排列，直到排到最高木板后，再从高度为 $1$ 的最矮木板 开始继续排列。

正当海蒂爷爷想用铁箍将木桶箍上时，小海蒂从远处跑来，递给爷爷一条新的木板请给海蒂爷爷想想办法，把新木板插入合适的位置，把奇怪的木桶完成。

如果新木板有多个位置可以插入时，则请放置在下标最小的位置。如 $[1$ $2$ $3$ $1]$ 插入 $1$ ，预期输出结果为 $[1$ $1$ $2$ $3$ $1]$ ，而不是 $[1$ $2$ $3$ $1$ $1]$ 。

输入描述

原始木板列表长度 $n$ 。$(2<n<=400)$

原始木板列表 $boards$ ，列表中每个元素表示木板高度，原始列表满足循环非递减条件。

$(1<=boards[i]<= 1000)$

新木板的长度 $newBoardLen$ 。$(1<=newBcardLene<=1000)$

输出描述

返回插入新数据后的 $boards$ 列表

样例1

输入

4
2 3 4 2
1

输出

2 3 4 1 2

说明

新增木板长度为 $1$ ，只有插在原第 $3$ 块和第四块本板之间，才能满足循环非递减规律所以新列表为 $2$ $3$ $4$ $1$ $2$

样例2

输入

4
1 2 3 1
1

输出

1 1 2 3 1

说明

新增木板长度为 $1$ ，插入木桶后，插在第一个 $1$ 的前后或者插在最后一个 $1$ 的前后，均满足循环非递减规律，按题目要求放置在下标最小位当即插入第一个 $1$ 前，所以新列表为 $1$ $1$ $2$ $3$ $1$