给你一个长度为 n 的整数数组 nums。

你从下标 0 开始，目标是到达下标 n - 1。

在任何下标 i 处，你可以执行以下操作之一：

• 移动到相邻格子：跳到下标 i + 1 或 i - 1，如果该下标在边界内。
• 质数传送：如果 nums[i] 是一个质数 p，你可以立即跳到任何满足 nums[j] % p == 0 的下标 j 处，且下标 j != i 。

返回到达下标 n - 1 所需的 最少 跳跃次数。

质数 是一个大于 1 的自然数，只有两个因子，1 和它本身。

示例 1:

示例 2:

示例 3:

提示:

• 1 <= n == nums.length <= 105
• 1 <= nums[i] <= 106

方法一：正向思维

整体是个 BFS 的框架。

设 $v=\textit{nums}[i]$。

• 如果 $v$ 不是质数，只能往 $i-1$ 和 $i+1$ 走一步。
• 如果 $v$ 是质数，除了能往 $i-1$ 和 $i+1$ 走一步，还能往 $v$ 在 $\textit{nums}$ 中的倍数那走一步。

怎么知道 $v$ 的倍数在哪？

预处理。在执行 BFS 之前，对于 $\textit{nums}$ 中的每个数 $x=\textit{nums}[i]$，把 $x$ 的的质因子 $p$ 和下标 $i$ 插入哈希表。哈希表的 key 是质数，value 是下标列表。

预处理后，从哈希表中可以直接获取到 $v$ 的倍数的下标。

注意遍历完下标列表后，要把列表从哈希表中删除（或者清空），避免反复遍历列表。比如一个有很多质数 $2$ 的数组，我们把这些 $2$ 的下标入队，出队的时候，不能重复遍历 $2$ 的倍数的下标列表。

代码实现时：

1. 预处理每个数的质因子列表，思路和埃氏筛是一样的。
2. 用双列表实现 BFS，原理请看【基础算法精讲 13】。当然，用队列也可以。

###py

# 预处理每个数的质因子列表，思路同埃氏筛
MX = 1_000_001
prime_factors = [[] for _ in range(MX)]
for i in range(2, MX):
    if not prime_factors[i]:  # i 是质数
        for j in range(i, MX, i):  # i 的倍数有质因子 i
            prime_factors[j].append(i)

class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            for p in prime_factors[x]:
                groups[p].append(i)  # 对于质数 p，可以跳到下标 i

        ans = 0
        vis = [False] * n
        vis[0] = True
        q = [0]

        while True:
            tmp = q
            q = []
            for i in tmp:
                if i == n - 1:
                    return ans
                idx = groups[nums[i]]
                idx.append(i + 1)
                if i:
                    idx.append(i - 1)
                for j in idx:  # 可以从 i 跳到 j
                    if not vis[j]:
                        vis[j] = True
                        q.append(j)
                idx.clear()  # 避免重复访问下标列表
            ans += 1

###java

class Solution {
    private static final int MX = 1_000_001;
    private static final List<Integer>[] primeFactors = new ArrayList[MX];
    private static boolean initialized = false;

    // 这样写比 static block 更快
    private void init() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.setAll(primeFactors, _ -> new ArrayList<>());
        // 预处理每个数的质因子列表，思路同埃氏筛
        for (int i = 2; i < MX; i++) {
            if (primeFactors[i].isEmpty()) { // i 是质数
                for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                    primeFactors[j].add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        init();

        int n = nums.length;
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int p : primeFactors[nums[i]]) {
                // 对于质数 p，可以跳到下标 i
                groups.computeIfAbsent(p, _ -> new ArrayList<>()).add(i);
            }
        }

        int ans = 0;
        boolean[] vis = new boolean[n];
        vis[0] = true;
        List<Integer> q = List.of(0);

        while (true) {
            List<Integer> tmp = q;
            q = new ArrayList<>();
            for (int i : tmp) {
                if (i == n - 1) {
                    return ans;
                }
                List<Integer> idx = groups.computeIfAbsent(nums[i], _ -> new ArrayList<>());
                idx.add(i + 1);
                if (i > 0) {
                    idx.add(i - 1);
                }
                for (int j : idx) { // 可以从 i 跳到 j
                    if (!vis[j]) {
                        vis[j] = true;
                        q.add(j);
                    }
                }
                idx.clear(); // 避免重复访问下标列表
            }
            ans++;
        }
    }
}

###cpp

const int MX = 1'000'001;
vector<int> prime_factors[MX];

int init = [] {
    // 预处理每个数的质因子列表，思路同埃氏筛
    for (int i = 2; i < MX; i++) {
        if (prime_factors[i].empty()) { // i 是质数
            for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                prime_factors[j].push_back(i);
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; i++) {
            for (int p : prime_factors[nums[i]]) {
                groups[p].push_back(i); // 对于质数 p，可以跳到下标 i
            }
        }

        int ans = 0;
        vector<int8_t> vis(n);
        vis[0] = true;
        vector<int> q = {0};

        while (true) {
            auto tmp = q;
            q.clear();
            for (int i : tmp) {
                if (i == n - 1) {
                    return ans;
                }
                auto& idx = groups[nums[i]];
                idx.push_back(i + 1);
                if (i > 0) {
                    idx.push_back(i - 1);
                }
                for (int j : idx) { // 可以从 i 跳到 j
                    if (!vis[j]) {
                        vis[j] = true;
                        q.push_back(j);
                    }
                }
                idx.clear(); // 避免重复访问下标列表
            }
            ans++;
        }
    }
};

###go

const mx = 1_000_001

var primeFactors = [mx][]int{}

func init() {
// 预处理每个数的质因子列表，思路同埃氏筛
for i := 2; i < mx; i++ {
if primeFactors[i] == nil { // i 是质数
for j := i; j < mx; j += i { // i 的倍数有质因子 i
primeFactors[j] = append(primeFactors[j], i)
}
}
}
}

func minJumps(nums []int) (ans int) {
n := len(nums)
groups := map[int][]int{}
for i, x := range nums {
for _, p := range primeFactors[x] {
groups[p] = append(groups[p], i) // 对于质数 p，可以跳到下标 i
}
}

vis := make([]bool, n)
vis[0] = true
q := []int{0}
for {
tmp := q
q = nil
for _, i := range tmp {
if i == n-1 {
return
}
idx := groups[nums[i]]
idx = append(idx, i+1)
if i > 0 {
idx = append(idx, i-1)
}
for _, j := range idx { // 可以从 i 跳到 j
if !vis[j] {
vis[j] = true
q = append(q, j)
}
}
delete(groups, nums[i]) // 避免重复访问下标列表
}
ans++
}
}

复杂度分析

预处理的时间和空间不计入。

• 时间复杂度：$\mathcal{O}(n\log U)$，其中 $n$ 是 $\textit{nums}$ 的长度，$U=\max(\textit{nums})$。循环次数取决于下标列表的总长度（这决定了 BFS 的循环次数）。在最坏情况下，构造这样一个 $\textit{nums}$ 数组，它含有 $\mathcal{O}(\log U)$ 个不同的质数，以及 $\mathcal{O}(n-\log U)$ 个有 $\mathcal{O}(\log U)$ 个质因子的数。此时下标列表的总长度为 $\mathcal{O}(n\log U)$，且 BFS 的循环次数也为 $\mathcal{O}(n\log U)$。
• 空间复杂度：$\mathcal{O}(n\log U)$。

方法二：逆向思维

从终点 $n-1$ 跳到起点 $0$。

跳跃规则反过来，从 $i$ 跳到 $\textit{nums}[i]$ 的质因子 $p$ 的下标。

在执行 BFS 之前，对于 $\textit{nums}$ 中的每个数 $x=\textit{nums}[i]$，如果 $x$ 是质数，把 $x$ 和下标 $i$ 插入哈希表。哈希表的 key 是质数，value 是下标列表。

###py

# 预处理每个数的质因子列表，思路同埃氏筛
MX = 1_000_001
prime_factors = [[] for _ in range(MX)]
for i in range(2, MX):
    if not prime_factors[i]:  # i 是质数
        for j in range(i, MX, i):  # i 的倍数有质因子 i
            prime_factors[j].append(i)

class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        groups = defaultdict(list)
        for i, x in enumerate(nums):
            if len(prime_factors[x]) == 1:  # x 是质数
                groups[x].append(i)

        ans = 0
        vis = [False] * n
        vis[-1] = True
        q = [n - 1]

        while True:
            tmp = q
            q = []
            for i in tmp:
                if i == 0:
                    return ans
                if not vis[i - 1]:
                    vis[i - 1] = True
                    q.append(i - 1)
                if i < n - 1 and not vis[i + 1]:
                    vis[i + 1] = True
                    q.append(i + 1)
                # 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
                for p in prime_factors[nums[i]]:
                    idx = groups[p]
                    for j in idx:
                        if not vis[j]:
                            vis[j] = True
                            q.append(j)
                    idx.clear()  # 避免重复访问下标列表
            ans += 1

###java

class Solution {
    private static final int MX = 1_000_001;
    private static final List<Integer>[] primeFactors = new ArrayList[MX];
    private static boolean initialized = false;

    // 这样写比 static block 更快
    private void init() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.setAll(primeFactors, _ -> new ArrayList<>());
        // 预处理每个数的质因子列表，思路同埃氏筛
        for (int i = 2; i < MX; i++) {
            if (primeFactors[i].isEmpty()) { // i 是质数
                for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                    primeFactors[j].add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        init();

        int n = nums.length;
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (primeFactors[x].size() == 1) { // x 是质数
                groups.computeIfAbsent(x, _ -> new ArrayList<>()).add(i);
            }
        }

        int ans = 0;
        boolean[] vis = new boolean[n];
        vis[n - 1] = true;
        List<Integer> q = List.of(n - 1);

        while (true) {
            List<Integer> tmp = q;
            q = new ArrayList<>();
            for (int i : tmp) {
                if (i == 0) {
                    return ans;
                }
                if (!vis[i - 1]) {
                    vis[i - 1] = true;
                    q.add(i - 1);
                }
                if (i + 1 < n && !vis[i + 1]) {
                    vis[i + 1] = true;
                    q.add(i + 1);
                }
                // 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
                for (int p : primeFactors[nums[i]]) {
                    List<Integer> idx = groups.remove(p); // 避免重复访问下标列表
                    if (idx != null) {
                        for (int j : idx) {
                            if (!vis[j]) {
                                vis[j] = true;
                                q.add(j);
                            }
                        }
                    }
                }
            }
            ans++;
        }
    }
}

###cpp

const int MX = 1'000'001;
vector<int> prime_factors[MX];

int init = [] {
    // 预处理每个数的质因子列表，思路同埃氏筛
    for (int i = 2; i < MX; i++) {
        if (prime_factors[i].empty()) { // i 是质数
            for (int j = i; j < MX; j += i) { // i 的倍数有质因子 i
                prime_factors[j].push_back(i);
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (prime_factors[x].size() == 1) { // x 是质数
                groups[x].push_back(i);
            }
        }

        int ans = 0;
        vector<int8_t> vis(n);
        vis[n - 1] = true;
        vector<int> q = {n - 1};

        while (true) {
            auto tmp = q;
            q.clear();
            for (int i : tmp) {
                if (i == 0) {
                    return ans;
                }
                if (!vis[i - 1]) {
                    vis[i - 1] = true;
                    q.push_back(i - 1);
                }
                if (i < n - 1 && !vis[i + 1]) {
                    vis[i + 1] = true;
                    q.push_back(i + 1);
                }
                // 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
                for (int p : prime_factors[nums[i]]) {
                    auto it = groups.find(p);
                    if (it != groups.end()) {
                        for (int j : it->second) {
                            if (!vis[j]) {
                                vis[j] = true;
                                q.push_back(j);
                            }
                        }
                        groups.erase(it); // 避免重复访问下标列表
                    }
                }
            }
            ans++;
        }
    }
};

###go

const mx = 1_000_001

var primeFactors = [mx][]int{}

func init() {
// 预处理每个数的质因子列表，思路同埃氏筛
for i := 2; i < mx; i++ {
if primeFactors[i] == nil { // i 是质数
for j := i; j < mx; j += i { // i 的倍数有质因子 i
primeFactors[j] = append(primeFactors[j], i)
}
}
}
}

func minJumps(nums []int) (ans int) {
n := len(nums)
groups := map[int][]int{}
for i, x := range nums {
if len(primeFactors[x]) == 1 { // x 是质数
groups[x] = append(groups[x], i)
}
}

vis := make([]bool, n)
vis[n-1] = true
q := []int{n - 1}
for {
tmp := q
q = nil
for _, i := range tmp {
if i == 0 {
return
}
if !vis[i-1] {
vis[i-1] = true
q = append(q, i-1)
}
if i < n-1 && !vis[i+1] {
vis[i+1] = true
q = append(q, i+1)
}
// 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j
for _, p := range primeFactors[nums[i]] {
for _, j := range groups[p] {
if !vis[j] {
vis[j] = true
q = append(q, j)
}
}
delete(groups, p) // 避免重复访问下标列表
}
}
ans++
}
}

复杂度分析

预处理的时间和空间不计入。

• 时间复杂度：$\mathcal{O}(n\log U)$，其中 $n$ 是 $\textit{nums}$ 的长度，$U=\max(\textit{nums})$。
• 空间复杂度：$\mathcal{O}(n)$。

相似题目

• 1345. 跳跃游戏 IV 1810

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

解法：01 BFS

相邻下标间的移动很好处理：将每个下标看成点，向相邻下标连权值为 $1$ 的边。

质数传送怎么办呢？将每个质数看成特殊点，值为质数的下标向对应特殊点连权值为 $1$ 的边。同时对每个下标的值进行质因数分解，从每个质因数特殊点向该下标连权值为 $0$ 的边即可。

因为边权都是 $0$ 和 $1$，可以用 01 BFS 求最短路。复杂度 $\mathcal{O}(X\log X + n\log X)$，其中 $X = 10^6$ 是权值。

参考代码（c++）

#define MAXA ((int) 1e6)
bool inited = false;
vector<int> fac[MAXA + 5];
void init() {
    if (inited) return;
    inited = true;
    // XlogX 预处理所有数的质因数
    for (int i = 2; i <= MAXA; i++) if (fac[i].empty()) for (int j = i; j <= MAXA; j += i) fac[j].push_back(i);
}

class Solution {
public:
    int minJumps(vector<int>& nums) {
        init();
        int n = nums.size();
        // 把要用到的质数都挑出来
        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++) if (fac[nums[i]].size() == 1) mp[nums[i]] = 1;
        int K = 0;
        for (auto &p : mp) p.second = n + K, K++;

        // 建图
        vector<int> e[n + K], v[n + K];
        for (int i = 0; i < n; i++) {
            // 相邻下标移动
            if (i > 0) e[i].push_back(i - 1), v[i].push_back(1);
            if (i + 1 < n) e[i].push_back(i + 1), v[i].push_back(1);
            // 质数传送：值为质数的下标向特殊点连边
            if (fac[nums[i]].size() == 1) e[i].push_back(mp[nums[i]]), v[i].push_back(1);
            // 质数传送：质因数特殊点向下标连边
            for (int x : fac[nums[i]]) if (mp.count(x)) {
                int idx = mp[x];
                e[idx].push_back(i);
                v[idx].push_back(0);
            }
        }

        // 模板：01 BFS
        int dis[n + K];
        memset(dis, -1, sizeof(dis));
        typedef pair<int, int> pii;
        deque<pii> dq;
        dq.push_back({0, 0}); dis[0] = 0;
        while (!dq.empty()) {
            pii p = dq.front(); dq.pop_front();
            int sn = p.first;
            if (dis[sn] != p.second) continue;
            if (sn == n - 1) return dis[sn];

            auto update = [&](int fn, int val) {
                int d = dis[sn] + val;
                if (dis[fn] == -1 || dis[fn] > d) {
                    dis[fn] = d;
                    if (val == 0) dq.push_front({fn, d});
                    else dq.push_back({fn, d});
                }
            };

            for (int i = 0; i < e[sn].size(); i++) update(e[sn][i], v[sn][i]);
        }
        return -1;
    }
};

给你一个整数数组 nums。

从任意下标 i 出发，你可以根据以下规则跳跃到另一个下标 j：

• 仅当 nums[j] < nums[i] 时，才允许跳跃到下标 j，其中 j > i。
• 仅当 nums[j] > nums[i] 时，才允许跳跃到下标 j，其中 j < i。

对于每个下标 i，找出从 i 出发且可以跳跃 任意 次，能够到达 nums 中的 最大值 是多少。

返回一个数组 ans，其中 ans[i] 是从下标 i 出发可以到达的最大值。

示例 1:

示例 2:

提示:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

想一想，是 $\textit{ans}[0]$ 更好算，还是 $\textit{ans}[n-1]$ 更好算？

对于 $i=n-1$ 来说，它一定能跳到 $\textit{nums}$ 的最大值：

• 如果最大值等于 $\textit{nums}[n-1]$，那么命题成立。
• 否则最大值比 $\textit{nums}[n-1]$ 大，且下标小于 $n-1$。根据规则，能从 $n-1$ 跳到。

所以 $\textit{ans}[n-1] = \max(\textit{nums})$。

而对于 $\textit{ans}[0]$，就变得非常复杂了。比如 $\textit{nums}=[6,8,5,9,7]$，从 $6$ 跳到 $9$ 的顺序为 $6\to 5\to 8\to 7\to 9$。

所以倒着思考更简单。

那么，每个数都能跳到最大值吗？什么情况下无法跳到最大值？

比如 $\textit{nums}=[3,1,2,30,10,20]$，无法从 $3,1,2$ 跳到 $30,10,20$。在 $2$ 和 $30$ 之间有一条「分界线」，如果分界线左边的最大值比分界线右边的最小值还小（或者相等），那么无法从分界线左边跳到分界线右边，所以分界线左边的数无法跳到 $\textit{nums}$ 的最大值。

一般地，设 $[0,i]$ 中的最大值为 $\textit{preMax}[i]$，$[i+1,n-1]$ 中的最小值为 $\textit{sufMin}[i+1]$。

• 如果 $\textit{preMax}[i] \le \textit{sufMin}[i+1]$，对于 $[0,i]$ 中的任意下标 $p$ 和 $[i+1,n-1]$ 中的任意下标 $q$，我们有 $\textit{nums}[p]\le \textit{preMax}[i]\le \textit{sufMin}[i+1]\le \textit{nums}[q]$，所以 $[0,i]$ 中的任何下标都无法跳到 $[i+1,n-1]$ 中。问题变成 $[0,i]$ 的子问题。类似前文 $i=n-1$ 的讨论，我们有 $\textit{ans}[i] = \textit{preMax}[i]$。
• 否则 $\textit{preMax}[i] > \textit{sufMin}[i+1]$，我们可以先从 $i$ 跳到 $\textit{preMax}[i]$ 的位置，再跳到 $\textit{sufMin}[i+1]$ 的位置，最后跳到 $i+1$。所以 $i+1$ 能跳到的数，$i$ 也能跳到（反之亦然），所以 $\textit{ans}[i] = \textit{ans}[i+1]$。

一般地，我们有如下状态转移方程

$$
\textit{ans}[i] =
\begin{cases}
\textit{preMax}[i], & \textit{preMax}[i] \le \textit{sufMin}[i+1] \
\textit{ans}[i+1], & \textit{preMax}[i] > \textit{sufMin}[i+1] \
\end{cases}
$$

规定 $\textit{sufMin}[n] = \infty$。

代码实现时，可以在计算 $\textit{ans}$ 的同时计算 $\textit{sufMin}$，所以 $\textit{sufMin}$ 可以简化成一个变量。

###py

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre_max = list(accumulate(nums, max))  # nums 的前缀最大值

        ans = [0] * n
        suf_min = inf
        for i in range(n - 1, -1, -1):
            ans[i] = pre_max[i] if pre_max[i] <= suf_min else ans[i + 1]
            suf_min = min(suf_min, nums[i])
        return ans

###py

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre_max = [0] * n
        pre_max[0] = nums[0]
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], nums[i])

        ans = [0] * n
        suf_min = inf
        for i in range(n - 1, -1, -1):
            ans[i] = pre_max[i] if pre_max[i] <= suf_min else ans[i + 1]
            suf_min = min(suf_min, nums[i])
        return ans

###java

class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            preMax[i] = Math.max(preMax[i - 1], nums[i]);
        }

        int[] ans = new int[n];
        int sufMin = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = preMax[i] <= sufMin ? preMax[i] : ans[i + 1];
            sufMin = Math.min(sufMin, nums[i]);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre_max(n);
        pre_max[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre_max[i] = max(pre_max[i - 1], nums[i]);
        }

        vector<int> ans(n);
        int suf_min = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] = pre_max[i] <= suf_min ? pre_max[i] : ans[i + 1];
            suf_min = min(suf_min, nums[i]);
        }
        return ans;
    }
};

###go

func maxValue(nums []int) []int {
n := len(nums)
preMax := make([]int, n)
preMax[0] = nums[0]
for i := 1; i < n; i++ {
preMax[i] = max(preMax[i-1], nums[i])
}

ans := make([]int, n)
sufMin := math.MaxInt
for i := n - 1; i >= 0; i-- {
if preMax[i] <= sufMin {
ans[i] = preMax[i]
} else {
ans[i] = ans[i+1]
}
sufMin = min(sufMin, nums[i])
}
return ans
}

也可以直接把答案保存在 $\textit{preMax}$ 中。

###py

# 手写 min max 更快
min = lambda a, b: b if b < a else a
max = lambda a, b: b if b > a else a

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre_max = list(accumulate(nums, max))  # nums 的前缀最大值

        suf_min = inf
        for i in range(n - 1, -1, -1):
            if pre_max[i] > suf_min:
                pre_max[i] = pre_max[i + 1]
            suf_min = min(suf_min, nums[i])
        return pre_max

###java

class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            preMax[i] = Math.max(preMax[i - 1], nums[i]);
        }

        int sufMin = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (preMax[i] > sufMin) {
                preMax[i] = preMax[i + 1];
            }
            sufMin = Math.min(sufMin, nums[i]);
        }
        return preMax;
    }
}

###cpp

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre_max(n);
        pre_max[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre_max[i] = max(pre_max[i - 1], nums[i]);
        }

        int suf_min = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            if (pre_max[i] > suf_min) {
                pre_max[i] = pre_max[i + 1];
            }
            suf_min = min(suf_min, nums[i]);
        }
        return pre_max;
    }
};

###go

func maxValue(nums []int) []int {
n := len(nums)
preMax := make([]int, n)
preMax[0] = nums[0]
for i := 1; i < n; i++ {
preMax[i] = max(preMax[i-1], nums[i])
}

sufMin := math.MaxInt
for i := n - 1; i >= 0; i-- {
if preMax[i] > sufMin {
preMax[i] = preMax[i+1]
}
sufMin = min(sufMin, nums[i])
}
return preMax
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

解法 1：观察并思考

设 $f(i)$ 表示前 $i$ 个元素的最大值，$g(i)$ 表示第 $i$ 到第 $n$ 个元素的最小值。

因为往后跳只能往更小的数走，所以如果 $f(i) \le g(i + 1)$，那么前 $i$ 个数不可能到达后面的数。然后注意到每次跳跃都是双向可通行的，所以后面的数也到不了前面的数。

反之，如果 $f(i) > g(i + 1)$，那么第 $i$ 个数可以先跳到前面的最大值 $f(i)$，然后跳到后面的最小值 $g(i + 1)$，然后再跳到第 $(i + 1)$ 个数。同样由于每次跳跃都是双向可通行的，第 $(i + 1)$ 个数也可以反过来到第 $i$ 个数。

因此，每个 $f(i) \le g(i + 1)$ 的位置就把整个序列分成了很多段，每一段的答案就是当前段的最大值。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();

        // f[i]：前 i 个元素的最大值
        // g[i]：第 i 到第 n 个元素的最小值
        int f[n], g[n + 1];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) f[i] = max(f[i - 1], nums[i]);
        g[n] = 1e9;
        for (int i = n - 1; i >= 0; i--) g[i] = min(g[i + 1], nums[i]);

        vector<int> ans(n);
        // now：当前段和左边所有段的最大值
        for (int i = n - 1, now = f[i]; i >= 0; i--) {
            // 分段了，更新最大值
            // f[i] 是递增的，所以前缀最大值就是当前段的最大值
            if (f[i] <= g[i + 1]) now = f[i];
            ans[i] = now;
        }
        return ans;
    }
};

解法 2：分类讨论 & 树状数组

观察不出这个性质怎么办呢？我们还可以分类讨论答案的相对位置。

对于每个数 $x$，显然它的答案 $y \ge x$。$y = x$ 的情况都不用跳，下面只考虑 $y > x$ 的情况。

假设它的答案 $y$ 在左边，因为往左跳是往更大的数走，所以直接跳过去即可。

如果它的答案 $y$ 在右边，那么我需要先跳到 $y$ 右边一个小于 $y$ 的值 $z$，才能跳到 $y$。

那是不是直接从 $x$ 跳到 $z$ 再到 $y$ 呢？不是，考虑这个例子 [3, 1, 4, 2]。我从 $1$ 是跳不到 $2$ 的，但是我可以先从 $1$ 到 $3$，再跳到 $2$，再跳到 $4$。因为往右跳是往更小的数走，所以 $x$ 越大，能跳到的 $z$ 就越多。所以先往左跳到最大值，然后再考虑往右怎么跳。

剩下的问题就是怎么求右边比 $x$ 小的数里，最大能跳到多少。用树状数组动态维护前缀 max 即可。

复杂度 $\mathcal{O}(n\log n)$。

参考代码（c++）

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();

        // 元素离散化
        map<int, int> mp;
        for (int x : nums) mp[x] = 1;
        int m = 0;
        for (auto &p : mp) p.second = ++m;
        for (int &x : nums) x = mp[x];
        int actual[m + 1];
        for (auto &p : mp) actual[p.second] = p.first;

        // 维护每个位置往左能跳到的最大值
        int f[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) f[i] = max(f[i - 1], nums[i]);

        // 树状数组模板开始

        int tree[m + 1];
        memset(tree, 0, sizeof(tree));
        
        auto lb = [&](int x) { return x & (-x); };

        auto update = [&](int pos, int val) {
            for (; pos <= m; pos += lb(pos)) tree[pos] = max(tree[pos], val);
        };

        auto query = [&](int pos) {
            int ret = 0;
            for (; pos; pos -= lb(pos)) ret = max(ret, tree[pos]);
            return ret;
        };

        // 树状数组模板结束

        vector<int> ans(n);
        for (int i = n - 1; i >= 0; i--) {
            // f[i] 是直接往左跳
            // query(f[i] - 1) 是先往左跳到最大值，然后看往右能到的最佳答案
            ans[i] = max(f[i], query(f[i] - 1));
            // 更新当前数能到的最佳答案
            update(nums[i], ans[i]);
        }
        for (auto &x : ans) x = actual[x];
        return ans;
    }
};

方法一：用队列维护空位

提示 $1$

当我们将盒子顺时针旋转之后，原先的「每一行」就变成了「每一列」。

由于石头受到重力只会竖直向下掉落，因此「每一列」之间都互不影响，我们可以依次计算「每一列」的结果，即原先的「每一行」的结果。

思路与算法

由于重力向下，那么我们应当从右向左遍历原先的「每一行」。

我们使用一个队列来存放一行中的空位：

• 当我们遍历到一块石头时，就从队首取出一个空位来放置这块石头。如果队列为空，那么说明右侧没有空位，这块石头不会下落；

• 当我们遍历到一个空位时，我们将其加入队列；

• 当我们遍历到一个障碍物时，需要将队列清空，障碍物右侧的空位都是不可用的。

在遍历完所有的行后，我们将矩阵顺时针旋转 $90$ 度，放入答案数组中即可。

代码

###C++

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size();
        int n = box[0].size();

        for (int i = 0; i < m; ++i) {
            deque<int> q;
            for (int j = n - 1; j >= 0; --j) {
                if (box[i][j] == '*') {
                    // 遇到障碍物，清空队列
                    q.clear();
                }
                else if (box[i][j] == '#') {
                    if (!q.empty()) {
                        // 如果队列不为空，石头就会下落
                        int pos = q.front();
                        q.pop_front();
                        box[i][pos] = '#';
                        box[i][j] = '.';
                        // 由于下落，石头变为空位，也需要加入队列
                        q.push_back(j);
                    }
                }
                else {
                    // 将空位加入队列
                    q.push_back(j);
                }
            }
        }

        // 将矩阵顺时针旋转 90 度放入答案
        vector<vector<char>> ans(n, vector<char>(m));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - i - 1] = box[i][j];
            }
        }
        return ans;
    }
};

###Python

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m, n = len(box), len(box[0])

        for i in range(m):
            q = deque()
            for j in range(n - 1, -1, -1):
                if box[i][j] == "*":
                    # 遇到障碍物，清空队列
                    q.clear()
                elif box[i][j] == "#":
                    if q:
                        # 如果队列不为空，石头就会下落
                        pos = q.popleft()
                        box[i][pos] = "#"
                        box[i][j] = "."
                        # 由于下落，石头变为空位，也需要加入队列
                        q.append(j)
                else:
                    # 将空位加入队列
                    q.append(j)

        # 将矩阵顺时针旋转 90 度放入答案
        ans = [[""] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][m - i - 1] = box[i][j]
        return ans

复杂度分析

• 时间复杂度：$O(mn)$。

• 空间复杂度：$O(n)$，即为队列需要使用的空间。这里我们不计算返回的答案使用的空间。

方法二：用指针维护空位

提示 $1$

在遍历完某一个位置之后，如果队列不为空，那么：

• 队尾一定是该位置；
• 队列中的位置一定是连续的。

提示 $1$ 解释

如果队列不为空，那么该位置一定是空位（要么原本就是空位，要么原本有一块石头下落，该位置变成了空位），因此该位置会被加入队列成为队尾。

如果队列中的位置不连续，假设队列中没有位置 $x$，但有小于 $x$ 和大于 $x$ 的位置，当我们在此之前遍历到位置 $x$ 时，$x$ 没有被放入队列，说明 $x$ 不是空位，并且那时的队列为空，这样队列中就不可能有大于 $x$ 的位置了，这就产生了矛盾。

思路与算法

根据提示 $1$，我们就无需显式地维护这个队列了。

如果队列不为空，那么队尾一定为当前位置，且队列中的位置连续。因此我们只需要维护队首对应的位置即可。

代码

###C++

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size();
        int n = box[0].size();

        for (int i = 0; i < m; ++i) {
            // 队首对应的位置
            int front_pos = n - 1;
            for (int j = n - 1; j >= 0; --j) {
                if (box[i][j] == '*') {
                    // 遇到障碍物，清空队列
                    front_pos = j - 1;
                }
                else if (box[i][j] == '#') {
                    if (front_pos > j) {
                        // 如果队列不为空，石头就会下落
                        box[i][front_pos] = '#';
                        box[i][j] = '.';
                        --front_pos;
                    }
                    else {
                        front_pos = j - 1;
                    }
                }
            }
        }

        // 将矩阵顺时针旋转 90 度放入答案
        vector<vector<char>> ans(n, vector<char>(m));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - i - 1] = box[i][j];
            }
        }
        return ans;
    }
};

###Python

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m, n = len(box), len(box[0])

        for i in range(m):
            # 队首对应的位置
            front_pos = n - 1
            for j in range(n - 1, -1, -1):
                if box[i][j] == "*":
                    # 遇到障碍物，清空队列
                    front_pos = j - 1
                elif box[i][j] == "#":
                    if front_pos > j:
                        # 如果队列不为空，石头就会下落
                        box[i][front_pos] = "#"
                        box[i][j] = "."
                        front_pos -= 1
                    else:
                        front_pos = j - 1

        # 将矩阵顺时针旋转 90 度放入答案
        ans = [[""] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][m - i - 1] = box[i][j]
        return ans

复杂度分析

• 时间复杂度：$O(mn)$。

• 空间复杂度：$O(1)$。这里我们不计算返回的答案使用的空间。

给你一个 m x n 的字符矩阵 boxGrid ，它表示一个箱子的侧视图。箱子的每一个格子可能为：

• '#' 表示石头
• '*' 表示固定的障碍物
• '.' 表示空位置

这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力 不会 影响障碍物的位置，同时箱子旋转不会产生惯性 ，也就是说石头的水平位置不会发生改变。

题目保证初始时 boxGrid 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。

请你返回一个 n x m 的矩阵，表示按照上述旋转后，箱子内的结果。

示例 1：

输入：box = [["#",".","#"]]
输出：[["."],
      ["#"],
      ["#"]]

示例 2：

输入：box = [["#",".","*","."],
            ["#","#","*","."]]
输出：[["#","."],
      ["#","#"],
      ["*","*"],
      [".","."]]

示例 3：

输入：box = [["#","#","*",".","*","."],
            ["#","#","#","*",".","."],
            ["#","#","#",".","#","."]]
输出：[[".","#","#"],
      [".","#","#"],
      ["#","#","*"],
      ["#","*","."],
      ["#",".","*"],
      ["#",".","."]]

提示：

• m == boxGrid.length
• n == boxGrid[i].length
• 1 <= m, n <= 500
• boxGrid[i][j] 只可能是 '#' ，'*' 或者 '.' 。

解题思路

我不明白为什么官方题解写的那么复杂，旋转前第 $i$ 行对应旋转后 $m-1-i$ 列，然后我们用一个 $idx$ 指针遍历旋转前第 $i$ 行的每一个元素，用一个变量 $stones$ 统计每段石头的数量，遇到障碍或结尾就开始把结果填充到 $m-1-i$ 列对应的位置 $[idx-stones,:idx)$，当然还要记得设置 $ans[idx][m-1-i]$ 为障碍物，然后循环执行上述操作直到这行遍历结束。
图片解说如下：

代码

###C++

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        const int m = (int)box.size(), n = (int)box[0].size();
        vector<vector<char>>ans(n,vector<char>(m,'.'));
        for (int i = 0; i < m; ++i) {
            int idx = 0;
            while (idx < n) {
                int stones = 0;
                while (idx < n && box[i][idx] != '*') {
                    if (box[i][idx] == '#') {
                        stones++;
                    }
                    idx++;
                }
                //fill stones into ans column m-1-i and rows range [idx-stones,idx)
                for (int j = idx - stones; j < idx; ++j) {
                    ans[j][m - 1 - i] = '#';
                }
                //fill obstacle into ans[idx][m-1-i]
                if (idx < n) {
                    ans[idx][m - 1 - i] = '*';
                }
                idx++;
            }
        }
        return ans;
    }
};

###Java

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        char[][] ans = new char[n][m];
        for(char[] row : ans){
            Arrays.fill(row, '.');
        }
        for (int i = 0; i < m; ++i) {
            int idx = 0;
            while (idx < n) {
                int stones = 0;
                while (idx < n && box[i][idx] != '*') {
                    if (box[i][idx] == '#') {
                        stones++;
                    }
                    idx++;
                }
                //fill stones into ans column m-1-i and rows range [idx-stones,idx)
                for (int j = idx - stones; j < idx; ++j) {
                    ans[j][m - 1 - i] = '#';
                }
                //fill obstacle into ans[idx][m-1-i]
                if (idx < n) {
                    ans[idx][m - 1 - i] = '*';
                }
                idx++;
            }
        }
        return ans;
    }
}

解题思路

对于原来的数组，只需要从右向左逐行处理，把石头放到该放的位置上去就可以了。

• 如果遇到石头，那么挪动石头到可放的位置。
• 如果遇到障碍物，那么更新可放的位置。

代码

###java

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        char[][] ans = new char[n][m];  // 用来构建返回值的二维数组
        // 首先逐行处理，把石头挪到该放的地方去
        for (int i = 0; i < m; ++i) {
            // 首先假设当前 i 行可放的位置是 pos
            int pos = n - 1;
            // 然后从右往左遍历，逐个更新石头的位置
            for (int j = n - 1; j >= 0; --j) {
                if (box[i][j] == '#') {
                    // 遇到了石头，先把它放到该放的位置去
                    box[i][pos--] = '#';
                    // 确保没有覆盖掉起始位置的石头，然后把挪动前的位置置为 空（.）
                    if (pos != j - 1) box[i][j] = '.';
                }
                // 如果遇到了障碍物，那么就更新可放的位置为障碍物的下一个位置（左边）
                else if (box[i][j] == '*') pos = j - 1;

            }
        }
        // 然后把更新后的位置映射到返回值中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - 1 - i] = box[i][j];
            }
        }
        return ans;
    }
}

方法一：正序遍历

$\textit{boxGrid}$ 的每一行互相独立，可以分别计算。

单独看每一行，我们需要知道每个障碍物（$\texttt{*}$）的左边有多少个石头（$\texttt{#}$）。

具体地，设当前障碍物到上一个障碍物之间有 $\textit{cnt}$ 个石头。那么旋转后，当前障碍物的左边有连续 $\textit{cnt}$ 个石头。据此：

• 在遍历过程中，统计石头的个数 $\textit{cnt}$。
• 如果下一个格子是障碍物，或者当前格子是最后一个格子，那么从当前格子往前填入连续 $\textit{cnt}$ 个石头，并重置计数器 $\textit{cnt}=0$。

细节：第 $i$ 行的格子旋转后在倒数第 $i$ 列，第 $j$ 列的格子旋转后在第 $j$ 行。所以 $(i,j)$ 旋转后位于 $(j,m-1-i)$。

class Solution:
    def rotateTheBox(self, boxGrid: list[list[str]]) -> list[list[str]]:
        m, n = len(boxGrid), len(boxGrid[0])
        ans = [[''] * m for _ in range(n)]

        for i, row in enumerate(boxGrid):
            cnt = 0
            for j, ch in enumerate(row):
                if ch == '#':  # 石头
                    cnt += 1
                    ch = '.'  # 先把石头清空
                ans[j][-1 - i] = ch
                if j == n - 1 or row[j + 1] == '*':  # 下一个格子是障碍物
                    # 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for k in range(j, j - cnt, -1):
                        ans[k][-1 - i] = '#'
                    cnt = 0  # 重置计数器

        return ans

class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length;
        int n = boxGrid[0].length;
        char[][] ans = new char[n][m];

        for (int i = 0; i < m; i++) {
            char[] row = boxGrid[i];
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                char ch = row[j];
                if (ch == '#') { // 石头
                    cnt++;
                    ch = '.'; // 先把石头清空
                }
                ans[j][m - 1 - i] = ch;
                if (j == n - 1 || row[j + 1] == '*') { // 下一个格子是障碍物
                    // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for (int k = j; k > j - cnt; k--) {
                        ans[k][m - 1 - i] = '#';
                    }
                    cnt = 0; // 重置计数器
                }
            }
        }

        return ans;
    }
}

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size(), n = boxGrid[0].size();
        vector ans(n, vector<char>(m));

        for (int i = 0; i < m; i++) {
            auto& row = boxGrid[i];
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                char ch = row[j];
                if (ch == '#') { // 石头
                    cnt++;
                    ch = '.'; // 先把石头清空
                }
                ans[j][m - 1 - i] = ch;
                if (j == n - 1 || row[j + 1] == '*') { // 下一个格子是障碍物
                    // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for (int k = j; k > j - cnt; k--) {
                        ans[k][m - 1 - i] = '#';
                    }
                    cnt = 0; // 重置计数器
                }
            }
        }

        return ans;
    }
};

char** rotateTheBox(char** boxGrid, int boxGridSize, int* boxGridColSize, int* returnSize, int** returnColumnSizes) {
    int m = boxGridSize, n = boxGridColSize[0];
    char** ans = malloc(n * sizeof(char*));
    *returnColumnSizes = malloc(n * sizeof(int));
    *returnSize = n;
    for (int i = 0; i < n; i++) {
        ans[i] = malloc(m * sizeof(char));
        (*returnColumnSizes)[i] = m;
    }

    for (int i = 0; i < m; i++) {
        char* row = boxGrid[i];
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            char ch = row[j];
            if (ch == '#') { // 石头
                cnt++;
                ch = '.'; // 先把石头清空
            }
            ans[j][m - 1 - i] = ch;
            if (j == n - 1 || row[j + 1] == '*') { // 下一个格子是障碍物
                // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                for (int k = j; k > j - cnt; k--) {
                    ans[k][m - 1 - i] = '#';
                }
                cnt = 0; // 重置计数器
            }
        }
    }

    return ans;
}

func rotateTheBox(boxGrid [][]byte) [][]byte {
m, n := len(boxGrid), len(boxGrid[0])
ans := make([][]byte, n)
for i := range ans {
ans[i] = make([]byte, m)
}

for i, row := range boxGrid {
cnt := 0
for j, ch := range row {
if ch == '#' { // 石头
cnt++
ch = '.' // 先把石头清空
}
ans[j][m-1-i] = ch
if j == n-1 || row[j+1] == '*' { // 下一个格子是障碍物
// 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
for k := j; k > j-cnt; k-- {
ans[k][m-1-i] = '#'
}
cnt = 0 // 重置计数器
}
}
}

return ans
}

var rotateTheBox = function(boxGrid) {
    const m = boxGrid.length, n = boxGrid[0].length;
    const ans = Array.from({ length: n }, () => Array(m));

    for (let i = 0; i < m; i++) {
        const row = boxGrid[i];
        let cnt = 0;
        for (let j = 0; j < n; j++) {
            let ch = row[j];
            if (ch === '#') { // 石头
                cnt++;
                ch = '.'; // 先把石头清空
            }
            ans[j][m - 1 - i] = ch;
            if (j === n - 1 || row[j + 1] === '*') { // 下一个格子是障碍物
                // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                for (let k = j; k > j - cnt; k--) {
                    ans[k][m - 1 - i] = '#';
                }
                cnt = 0; // 重置计数器
            }
        }
    }

    return ans;
};

impl Solution {
    pub fn rotate_the_box(box_grid: Vec<Vec<char>>) -> Vec<Vec<char>> {
        let m = box_grid.len();
        let n = box_grid[0].len();
        let mut ans = vec![vec!['\0'; m]; n];

        for (i, row) in box_grid.iter().enumerate() {
            let mut cnt = 0;
            for (j, &ch) in row.into_iter().enumerate() {
                let mut ch = ch;
                if ch == '#' { // 石头
                    cnt += 1;
                    ch = '.'; // 先把石头清空
                }
                ans[j][m - 1 - i] = ch;
                if j == n - 1 || row[j + 1] == '*' { // 下一个格子是障碍物
                    // 石头垂直掉落后，从 j 往前 cnt 个格子都是石头
                    for k in j - cnt + 1..=j {
                        ans[k][m - 1 - i] = '#';
                    }
                    cnt = 0; // 重置计数器
                }
            }
        }

        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{boxGrid}$ 的行数和列数。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。

方法二：倒序遍历 + 双指针

对于每一行 $\textit{row}$，倒着遍历，我们可以直接确定每个石头落入的位置：

• 如果 $\textit{row}[j]$ 是障碍物，那么它左边最近的石头，在旋转后掉落到 $\textit{row}[j-1]$。我们用一个变量 $k$ 维护石头掉落后的位置，如果 $\textit{row}[j]$ 是障碍物，那么更新 $\textit{k} = j-1$。注：如果 $\textit{row}[j]$ 左边最近的不是石头而是障碍物，那么 $k$ 会继续更新，无需担心石头落到错误的位置。
• 如果 $\textit{row}[j]$ 是石头，那么它掉落到 $\textit{row}[\textit{k}]$。然后把 $k$ 减一，表示左边下一块石头掉落后的位置。

class Solution:
    def rotateTheBox(self, boxGrid: list[list[str]]) -> list[list[str]]:
        m, n = len(boxGrid), len(boxGrid[0])
        ans = [['.'] * m for _ in range(n)]

        for i, row in enumerate(boxGrid):
            k = n - 1
            for j in range(n - 1, -1, -1):
                if row[j] == '*':  # 障碍物
                    ans[j][-1 - i] = '*'
                    k = j - 1  # 障碍物左边最近的石头，在旋转后掉落到 j-1
                elif row[j] == '#':  # 石头
                    ans[k][-1 - i] = '#'  # 旋转后，石头掉落到 k
                    k -= 1

        return ans

class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length;
        int n = boxGrid[0].length;
        char[][] ans = new char[n][m];
        for (char[] row : ans) {
            Arrays.fill(row, '.');
        }

        for (int i = 0; i < m; i++) {
            char[] row = boxGrid[i];
            int k = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (row[j] == '*') { // 障碍物
                    ans[j][m - 1 - i] = '*';
                    k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
                } else if (row[j] == '#') { // 石头
                    ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                    k--;
                }
            }
        }

        return ans;
    }
}

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size(), n = boxGrid[0].size();
        vector ans(n, vector<char>(m, '.'));

        for (int i = 0; i < m; i++) {
            auto& row = boxGrid[i];
            int k = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (row[j] == '*') { // 障碍物
                    ans[j][m - 1 - i] = '*';
                    k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
                } else if (row[j] == '#') { // 石头
                    ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                    k--;
                }
            }
        }

        return ans;
    }
};

char** rotateTheBox(char** boxGrid, int boxGridSize, int* boxGridColSize, int* returnSize, int** returnColumnSizes) {
    int m = boxGridSize, n = boxGridColSize[0];
    char** ans = malloc(n * sizeof(char*));
    *returnColumnSizes = malloc(n * sizeof(int));
    *returnSize = n;
    for (int i = 0; i < n; i++) {
        ans[i] = malloc(m * sizeof(char));
        memset(ans[i], '.', m * sizeof(char));
        (*returnColumnSizes)[i] = m;
    }

    for (int i = 0; i < m; i++) {
        char* row = boxGrid[i];
        int k = n - 1;
        for (int j = n - 1; j >= 0; j--) {
            if (row[j] == '*') { // 障碍物
                ans[j][m - 1 - i] = '*';
                k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
            } else if (row[j] == '#') { // 石头
                ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                k--;
            }
        }
    }

    return ans;
}

func rotateTheBox(boxGrid [][]byte) [][]byte {
m, n := len(boxGrid), len(boxGrid[0])
ans := make([][]byte, n)
for i := range ans {
ans[i] = bytes.Repeat([]byte{'.'}, m)
}

for i, row := range boxGrid {
k := n - 1
for j := n - 1; j >= 0; j-- {
if row[j] == '*' { // 障碍物
ans[j][m-1-i] = '*'
k = j - 1 // 障碍物左边最近的石头，在旋转后掉落到 j-1
} else if row[j] == '#' { // 石头
ans[k][m-1-i] = '#' // 旋转后，石头掉落到 k
k--
}
}
}

return ans
}

var rotateTheBox = function(boxGrid) {
    const m = boxGrid.length, n = boxGrid[0].length;
    const ans = Array.from({ length: n }, () => Array(m).fill('.'));

    for (let i = 0; i < m; i++) {
        const row = boxGrid[i];
        let k = n - 1;
        for (let j = n - 1; j >= 0; j--) {
            if (row[j] === '*') { // 障碍物
                ans[j][m - 1 - i] = '*';
                k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
            } else if (row[j] === '#') { // 石头
                ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                k--;
            }
        }
    }

    return ans;
};

impl Solution {
    pub fn rotate_the_box(box_grid: Vec<Vec<char>>) -> Vec<Vec<char>> {
        let m = box_grid.len();
        let n = box_grid[0].len();
        let mut ans = vec![vec!['.'; m]; n];

        for (i, row) in box_grid.into_iter().enumerate() {
            let mut k = n - 1;
            for (j, ch) in row.into_iter().enumerate().rev() {
                if ch == '*' { // 障碍物
                    ans[j][m - 1 - i] = '*';
                    k = j - 1; // 障碍物左边最近的石头，在旋转后掉落到 j-1
                } else if ch == '#' { // 石头
                    ans[k][m - 1 - i] = '#'; // 旋转后，石头掉落到 k
                    k -= 1;
                }
            }
        }

        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{boxGrid}$ 的行数和列数。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。

专题训练

见下面双指针题单的「六、分组循环」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

示例 1 的链表长为 $5$，$k=2$。旋转后，原链表的倒数第 $k$ 个节点，成为新链表的头节点。

把 $1\to 2\to 3\to 4\to 5$ 变成 $4\to 5\to 1\to 2\to 3$，我们需要：

1. 首尾相连，把 $5$ 和 $1$ 连起来。遍历链表即可找到尾节点。
2. 断开倒数第 $k+1$ 个节点和倒数第 $k$ 个节点，即断开 $3\to 4$。

本题 $k$ 可能很大，我们需要先求出链表的长度 $n$，然后把 $k$ 更新为 $k\bmod n$。这是因为链表旋转 $n$ 次没变，旋转 $n+1$ 次等同于旋转 $1$ 次，依此类推，旋转 $k$ 次等价于旋转 $k\bmod n$ 次。

倒数第 $k+1$ 个节点即正数第 $n-k$ 个节点。从头节点开始，向后移动 $n-k-1$ 次，即为正数第 $n-k$ 个节点。

###py

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None:
            return None

        # 1. 计算链表长度，并找到尾节点
        length = 1
        tail = head
        while tail.next:
            length += 1
            tail = tail.next
        k %= length

        # 2. 首尾相连
        tail.next = head

        # 3. 找倒数第 k+1 个节点，作为新链表的尾节点
        new_tail = head
        for _ in range(length - k - 1):
            new_tail = new_tail.next

        # 4. 断开倒数第 k+1 个节点（new_tail）和倒数第 k 个节点（new_head）
        new_head = new_tail.next
        new_tail.next = None
        return new_head

###java

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        // 1. 计算链表长度，并找到尾节点
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            length++;
            tail = tail.next;
        }
        k %= length;

        // 2. 首尾相连
        tail.next = head;

        // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
        ListNode newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail.next;
        }

        // 4. 断开倒数第 k+1 个节点（newTail）和倒数第 k 个节点（newHead）
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}

###cpp

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr) {
            return nullptr;
        }

        // 1. 计算链表长度，并找到尾节点
        int length = 1;
        ListNode* tail = head;
        while (tail->next) {
            length++;
            tail = tail->next;
        }
        k %= length;

        // 2. 首尾相连
        tail->next = head;

        // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
        ListNode* new_tail = head;
        for (int i = 0; i < length - k - 1; i++) {
            new_tail = new_tail->next;
        }

        // 4. 断开倒数第 k+1 个节点（new_tail）和倒数第 k 个节点（new_head）
        ListNode* new_head = new_tail->next;
        new_tail->next = nullptr;
        return new_head;
    }
};

###c

struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (head == NULL) {
        return NULL;
    }

    // 1. 计算链表长度，并找到尾节点
    int length = 1;
    struct ListNode* tail = head;
    while (tail->next) {
        length++;
        tail = tail->next;
    }
    k %= length;

    // 2. 首尾相连
    tail->next = head;

    // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
    struct ListNode* new_tail = head;
    for (int i = 0; i < length - k - 1; i++) {
        new_tail = new_tail->next;
    }

    // 4. 断开倒数第 k+1 个节点（new_tail）和倒数第 k 个节点（new_head）
    struct ListNode* new_head = new_tail->next;
    new_tail->next = NULL;
    return new_head;
}

###go

func rotateRight(head *ListNode, k int) *ListNode {
if head == nil {
return nil
}

// 1. 计算链表长度，并找到尾节点
length := 1
tail := head
for tail.Next != nil {
length++
tail = tail.Next
}
k %= length

// 2. 首尾相连
tail.Next = head

// 3. 找倒数第 k+1 个节点，作为新链表的尾节点
newTail := head
for range length - k - 1 {
newTail = newTail.Next
}

// 4. 断开倒数第 k+1 个节点（newTail）和倒数第 k 个节点（newHead）
newHead := newTail.Next
newTail.Next = nil
return newHead
}

###js

var rotateRight = function(head, k) {
    if (head === null) {
        return null;
    }

    // 1. 计算链表长度，并找到尾节点
    let length = 1;
    let tail = head;
    while (tail.next !== null) {
        length++;
        tail = tail.next;
    }
    k %= length;

    // 2. 首尾相连
    tail.next = head;

    // 3. 找倒数第 k+1 个节点，作为新链表的尾节点
    let newTail = head;
    for (let i = 0; i < length - k - 1; i++) {
        newTail = newTail.next;
    }

    // 4. 断开倒数第 k+1 个节点（newTail）和倒数第 k 个节点（newHead）
    const newHead = newTail.next;
    newTail.next = null;
    return newHead;
};

###rust

impl Solution {
    pub fn rotate_right(mut head: Option<Box<ListNode>>, mut k: i32) -> Option<Box<ListNode>> {
        if head.is_none() {
            return head;
        }

        // 1. 计算链表长度
        let mut length = 0;
        let mut cur = &head;
        while let Some(node) = cur {
            length += 1;
            cur = &node.next;
        }

        k %= length;
        if k == 0 { // 链表不变
            return head;
        }

        // 2. 找倒数第 k 个节点
        let mut cur = &mut head;
        for _ in 0..length - k {
            cur = &mut cur.as_mut()?.next;
        }

        // 3. 断开倒数第 k+1 个节点和倒数第 k 个节点（new_head）
        let mut new_head = cur.take();

        // 4. 首尾相连
        let mut tail = &mut new_head;
        while !tail.as_mut()?.next.is_none() {
            tail = &mut tail.as_mut()?.next;
        }
        tail.as_mut()?.next = head;

        new_head
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是链表的长度。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

1、思路

(模拟) $O(n)$

给你一个链表的头节点 head ，然后将链表每个节点向右移动 k 个位置。

样例：

{:width="70%"}

如样例所示，head = [1,2,3,4,5]，k = 2，我们输出[4,5,1,2,3]。下面来讲解模拟的做法。

假设链表的长度为n，为了将链表每个节点向右移动 k 个位置，我们只需要将链表的后 k % n个节点移动到链表的最前面，然后将链表的后k % n个节点和前 n - k个节点连接到一块即可。

具体过程如下：

1、首先遍历整个链表，求出链表的长度n，并找出链表的尾节点tail。

{:width="70%"}

2、由于k可能很大，所以我们令 k = k % n，然后再次从头节点head开始遍历，找到第n - k个节点p，那么1 ~ p是链表的前 n - k个节点，p+1 ~ n是链表的后k个节点。

{:width="70%"}

3、接下来就是依次执行 tail->next = head，head = p->next，p->next = nullptr，将链表的后k个节点和前 n - k个节点拼接到一块，并让head指向新的头节点(p->next)，新的尾节点即p节点的next指针指向null。

{:width="70%"}

4、最后返回链表的新的头节点head。

时间复杂度分析： 链表一共被遍历两次，因此总的时间复杂度为$O(n)$，$n$是链表的长度。

2、c++代码

###c

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || !k)  return head;
        int n = 0;        //链表的长度
        ListNode* tail;   //尾节点
        for(ListNode* p = head; p ; p = p->next){
            tail = p;
            n++;
        }
        k %= n;  
        ListNode* p = head;
        for(int i = 0; i < n - k - 1; i++)   p = p->next;  //找到链表的第n-k个节点
        tail->next = head;
        head = p->next;
        p->next = nullptr;
        return head;     //返回新的头节点
    }
};

3、java代码

###javascript

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null|| k == 0)  return head;
        int n = 0;   //链表的长度
        ListNode tail = null;  //尾节点
        for(ListNode p = head; p != null ; p = p.next){
            tail = p;
            n++;
        }
        k %= n;
        ListNode p = head;
        for(int i = 0; i < n - k - 1; i++)  p = p.next;   //找到链表的第n-k个节点
        tail.next = head;
        head = p.next;
        p.next = null;
        return head;  //返回新的头节点
    }
}

方法一：闭合为环

思路及算法

记给定链表的长度为 $n$，注意到当向右移动的次数 $k \geq n$ 时，我们仅需要向右移动 $k \bmod n$ 次即可。因为每 $n$ 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 $(n - 1) - (k \bmod n)$ 个节点（从 $0$ 开始计数）。

这样，我们可以先将给定的链表连接成环，然后将指定位置断开。

具体代码中，我们首先计算出链表的长度 $n$，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第 $(n - 1) - (k \bmod n)$ 个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。

特别地，当链表长度不大于 $1$，或者 $k$ 为 $n$ 的倍数时，新链表将与原链表相同，我们无需进行任何处理。

代码

###C++

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr) {
            return head;
        }
        int n = 1;
        ListNode* iter = head;
        while (iter->next != nullptr) {
            iter = iter->next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter->next = head;
        while (add--) {
            iter = iter->next;
        }
        ListNode* ret = iter->next;
        iter->next = nullptr;
        return ret;
    }
};

###Java

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter.next = head;
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }
}

###Python

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0 or not head or not head.next:
            return head
        
        n = 1
        cur = head
        while cur.next:
            cur = cur.next
            n += 1
        
        if (add := n - k % n) == n:
            return head
        
        cur.next = head
        while add:
            cur = cur.next
            add -= 1
        
        ret = cur.next
        cur.next = None
        return ret

###JavaScript

var rotateRight = function(head, k) {
    if (k === 0 || !head || !head.next) {
        return head;
    }
    let n = 1;
    let cur = head;
    while (cur.next) {
        cur = cur.next;
        n++;
    }

    let add = n - k % n;
    if (add === n) {
        return head;
    }

    cur.next = head;
    while (add) {
        cur = cur.next;
        add--;
    }

    const ret = cur.next;
    cur.next = null;
    return ret;
};

###go

func rotateRight(head *ListNode, k int) *ListNode {
    if k == 0 || head == nil || head.Next == nil {
        return head
    }
    n := 1
    iter := head
    for iter.Next != nil {
        iter = iter.Next
        n++
    }
    add := n - k%n
    if add == n {
        return head
    }
    iter.Next = head
    for add > 0 {
        iter = iter.Next
        add--
    }
    ret := iter.Next
    iter.Next = nil
    return ret
}

###C

struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (k == 0 || head == NULL || head->next == NULL) {
        return head;
    }
    int n = 1;
    struct ListNode* iter = head;
    while (iter->next != NULL) {
        iter = iter->next;
        n++;
    }
    int add = n - k % n;
    if (add == n) {
        return head;
    }
    iter->next = head;
    while (add--) {
        iter = iter->next;
    }
    struct ListNode* ret = iter->next;
    iter->next = NULL;
    return ret;
}

复杂度分析

• 时间复杂度：$O(n)$，最坏情况下，我们需要遍历该链表两次。

• 空间复杂度：$O(1)$，我们只需要常数的空间存储若干变量。

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000