登录观察并思考 or (分类讨论 & 树状数组)
解法 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;
}
};
