Problem: 3660. 跳跃游戏 9

思路

从题意知，从i位置向右跳转只能跳转到比nums[i]小的位置，从i位置向左跳转只能跳转到nums[i]大的位置。

那么，如果i位置右边的所有值都比i位置左边的所有值都要大，那么从i位置跳转，无法向右边跳转，只能向左边跳转。

因此，从i位置处跳转能到达的最大值在i位置左边数组里面，能到达的最大值就是i位置左边所有值中的最大值。

那么什么时候i位置右边的所有值都比i位置左边的所有值要大呢？i位置左边的最大值都要比i位置右边的最小值要小的时候。

我们设f[i]为0i位置中最大的值，g[i]表示i+1n位置中最小的值。假设我们从n-1向0遍历。

  • 如果f[i]<=g[i+1]，那么ans[i]=f[i]。

  • 如果f[i]>g[i+1]，这个时候最大值就不是f[i]了。

    • 此时最大值可能分布在i左边或者i右边的位置。i位置左边的最大值已经找出来了，就是f[i]，所以不妨先从i位置跳转到f[i]所在的那个位置处。
    • 又因为f[i]>g[i+1]，所以又能从f[i]所在的位置跳转到g[i+1]所在的位置。
    • 而g[i+1]位置处又是i+1~n中值最小的位置处，我们又能从g[i+1]处向左跳转到i+1处。也就是说，当f[i]>g[i+1]的时候，我们能从i位置跳转到到i+1位置。
    • 我们要求从i位置能跳转达到的最大值，我们可以先从i跳转到i+1位置，再从i+1从跳转求最大值。而ans[i+1]我们已经求解出来了。那么ans[i]=ans[i+1]。

复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1) （直接在原数组nums上滚动更新即可）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        f[0] = nums[0];
        for(int i = 1;i < n;i ++){
            f[i] = Math.max(f[i-1],nums[i]);
        }

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

        int ans = g[n-1];
        for(int i = n-1;i >= 0;i --){
            if(f[i] <= g[i+1]){
                ans = f[i];
            }
            nums[i] = ans;
        }
        return nums;
    }
}