2297. Jump Game IX

You are given a 0-indexed integer array nums of length n. You are initially standing at index 0. You can jump from index i to index j where i < j if:

• nums[i] <= nums[j] and nums[k] < nums[i] for all indexes k in the range i < k < j, or
• nums[i] > nums[j] and nums[k] >= nums[i] for all indexes k in the range i < k < j.

You are also given an integer array costs of length n where costs[i] denotes the cost of jumping to index i.

Return the minimum cost to jump to the index n - 1.

class Solution {
public:
    long long minCost(vector<int>& A, vector<int>& C) {
        long long n = A.size();
        vector<int> jump1(n), jump2(n);
        vector<int> st1, st2;

        for(int i = 0; i < n; i++) {
            while(!st1.empty() and A[st1.back()] <= A[i]) {
                jump1[st1.back()] = i;
                st1.pop_back();
            }
            while(!st2.empty() and A[st2.back()] > A[i]) {
                jump2[st2.back()] = i;
                st2.pop_back();
            }
            st1.push_back(i);
            st2.push_back(i);
        }
        vector<long long> dp(n, LLONG_MAX);
        dp[0] = 0;
        
        for(int i = 0; i < n; i++) {
            if(i + 1 < n) dp[i + 1] = min(dp[i + 1], dp[i] + C[i + 1]);
            dp[jump1[i]] = min(dp[jump1[i]], dp[i] + C[jump1[i]]);
            dp[jump2[i]] = min(dp[jump2[i]], dp[i] + C[jump2[i]]);
        }
        
        return dp.back();
    }
};