解题思路

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

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

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

1. 普通段（不跨越断点）：若 prev <= curr，则当 prev <= x <= curr 时可以插入到 i。
2. 断点段（最大到最小处）：若 prev > curr，则当 x >= prev（作为新的最大）或 x <= curr（作为新的最小）时可以插入到 i。
3. 若一圈都没有匹配（只会发生在“所有元素相等且 x 不等于它们”的情况），任意位置都合法，按题意取下标最小，放到 0 号位即可。

从 i=0 递增扫描，第一次满足条件的位置即是最小下标的可插位置。

算法要点：一次线性扫描 + O(1) 条件判断，无需显式找旋转点、无需旋转数组。

复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(1) 额外空间（除返回的新数组/列表外）。

代码实现

Python

# 功能函数：在循环非递减数组中插入一个值，返回新列表
def insert_board(boards, x):
    n = len(boards)
    if n == 0:
        return [x]
    # 线性扫描，寻找最小下标可插位置
    for i in range(n):
        prev = boards[(i - 1) % n]   # 前一个元素（环形）
        curr = boards[i]             # 当前位置元素
        if prev <= curr:
            # 普通非递减段：x 介于 prev 和 curr 之间即可
            if prev <= x <= curr:
                return boards[:i] + [x] + boards[i:]
        else:
            # 断点（最大->最小）：x 是新的最大或新的最小都可以
            if x >= prev or x <= curr:
                return boards[:i] + [x] + boards[i:]
    # 若未命中（如全相等且 x 不等），按题意取下标最小，插到 0 号位
    return [x] + boards

def main():
    import sys
    data = sys.stdin.read().strip().split()
    # 输入格式：
    # n
    # boards（n 个整数，空格分隔）
    # newBoardLen
    idx = 0
    n = int(data[idx]); idx += 1
    boards = list(map(int, data[idx:idx+n])); idx += n
    x = int(data[idx])
    ans = insert_board(boards, x)
    # 按空格输出
    print(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// ACM 风格主类名固定为 Main
public class Main {

    // 功能函数：在循环非递减数组中插入一个值，返回新数组
    public static int[] insertBoard(int[] a, int x) {
        int n = a.length;
        if (n == 0) {
            return new int[]{x};
        }
        // 线性扫描，寻找最小下标可插位置
        for (int i = 0; i < n; i++) {
            int prev = a[(i - 1 + n) % n]; // 环形前一个
            int curr = a[i];
            if (prev <= curr) {
                // 普通非递减段
                if (prev <= x && x <= curr) {
                    return insertAt(a, i, x);
                }
            } else {
                // 断点（最大->最小）
                if (x >= prev || x <= curr) {
                    return insertAt(a, i, x);
                }
            }
        }
        // 未命中（如全相等且 x 不等），按题意插到 0 号位
        return insertAt(a, 0, x);
    }

    // 辅助：在下标 pos 前插入 x
    private static int[] insertAt(int[] a, int pos, int x) {
        int n = a.length;
        int[] b = new int[n + 1];
        // 拷贝 [0, pos)
        for (int i = 0; i < pos; i++) {
            b[i] = a[i];
        }
        b[pos] = x;
        // 拷贝 [pos, n)
        for (int i = pos; i < n; i++) {
            b[i + 1] = a[i];
        }
        return b;
    }

    public static void main(String[] args) throws IOException {
        // 根据数据范围，普通 IO 足够
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;

        // 读取 n
        line = br.readLine();
        int n = Integer.parseInt(line.trim());

        // 读取 boards（用空格分割）
        line = br.readLine();
        StringTokenizer st = new StringTokenizer(line);
        int[] boards = new int[n];
        for (int i = 0; i < n; i++) {
            if (st.hasMoreTokens()) {
                boards[i] = Integer.parseInt(st.nextToken());
            }
        }

        // 读取新木板长度
        line = br.readLine();
        int x = Integer.parseInt(line.trim());

        int[] ans = insertBoard(boards, x);

        // 按空格输出
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            if (i > 0) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 功能函数：在循环非递减数组中插入一个值，返回新数组
vector<int> insertBoard(const vector<int>& a, int x) {
    int n = (int)a.size();
    if (n == 0) return vector<int>{x};
    // 线性扫描寻找最小下标可插位置
    for (int i = 0; i < n; ++i) {
        int prev = a[(i - 1 + n) % n]; // 环形前一个
        int curr = a[i];
        if (prev <= curr) {
            // 普通非递减段
            if (prev <= x && x <= curr) {
                vector<int> b; b.reserve(n + 1);
                // [0, i)
                for (int k = 0; k < i; ++k) b.push_back(a[k]);
                b.push_back(x);
                // [i, n)
                for (int k = i; k < n; ++k) b.push_back(a[k]);
                return b;
            }
        } else {
            // 断点（最大->最小）
            if (x >= prev || x <= curr) {
                vector<int> b; b.reserve(n + 1);
                for (int k = 0; k < i; ++k) b.push_back(a[k]);
                b.push_back(x);
                for (int k = i; k < n; ++k) b.push_back(a[k]);
                return b;
            }
        }
    }
    // 未命中（如全相等且 x 不等），按题意插到 0 号位
    vector<int> b; b.reserve(n + 1);
    b.push_back(x);
    for (int k = 0; k < n; ++k) b.push_back(a[k]);
    return b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;          // 读 n
    vector<int> boards(n);
    for (int i = 0; i < n; ++i) cin >> boards[i];  // 读 boards
    int x;
    cin >> x;                           // 读新木板长度

    vector<int> ans = insertBoard(boards, x);

    // 按空格输出
    for (int i = 0; i < (int)ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << "\n";
    return 0;
}

题目内容

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

他去山里砍了一些木柴加工成高矮不一的木板，然后他把木板按高矮排好顺序，依次取出，竖在地上，排列成一个圆桶状。该圆桶满足循环单调非递减规律(即从第 $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$