2297. Jump Game IX

 一刷 06/2022

Version #1 Two Stacks + DP

Iterate了3遍，可以化简成one pass, 但是思路没有这个straight forwad

Time O(N) - 因为根据定义每一个node最多只有2 children，所以dp用时是2N

Space O(N)

Runtime: 167 ms, faster than 48.39% of Java online submissions for Jump Game IX.

Memory Usage: 74.9 MB, less than 85.48% of Java online submissions for Jump Game IX.

class Solution {

    public long minCost(int[] nums, int[] costs) {

        // nums[i] <= nums[j] and nums[k] < nums[i] for all indexes k in the range i < k < j

        // The first index that has element larger than or equals to nums[i] on its right

        // keep a decreasing stack

        // when a new element comes, if it is larget than or equals to the peek of the stack, it means we can jump from the peek of the stack to the current element

        // descending stack of nums index

        if (nums == null || nums.length == 0) {

            return 0l;

        }

        // dp[i] - The min cost to jump to index i

        long[] dp = new long[nums.length];

        List<Integer>[] graph = new ArrayList[nums.length];

        for (int i = 0; i < nums.length; i++) {

            graph[i] = new ArrayList<>();

            dp[i] = Long.MAX_VALUE;

        }

        Stack<Integer> descStack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {

            while (!descStack.isEmpty() && nums[descStack.peek()] <= nums[i]) {

                graph[descStack.pop()].add(i);

            }

            descStack.push(i);

        }

        // nums[i] > nums[j] and nums[k] >= nums[i] for all indexes k in the range i < k < j

        // The first index that has element smaller than nums[i] on its right

        // keep a increasing stack

        Stack<Integer> increStack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {

            while (!increStack.isEmpty() && nums[increStack.peek()] > nums[i]) {

                graph[increStack.pop()].add(i);

            }

            increStack.push(i);

        }

        dp[0] = 0l;

        for (int i = 0; i < nums.length; i++) {

            for (int next : graph[i]) {

                dp[next] = Math.min(dp[next], costs[next] + dp[i]);

            }

        }

        return dp[nums.length - 1];

    }

}