2297 solved.

liuyubobobo · liuyubobobo · commit 1d7e7aa8dfd5 · 2022-06-09T17:28:25.000-07:00
diff --git a/2001-2500/2297-Jump-Game-IX/cpp-2297/CMakeLists.txt b/2001-2500/2297-Jump-Game-IX/cpp-2297/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_2297)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_2297 main.cpp)
diff --git a/2001-2500/2297-Jump-Game-IX/cpp-2297/main.cpp b/2001-2500/2297-Jump-Game-IX/cpp-2297/main.cpp
@@ -0,0 +1,66 @@
+/// Source : https://leetcode.com/problems/jump-game-ix/
+/// Author : liuyubobobo
+/// Time   : 2022-06-09
+
+#include <iostream>
+#include <vector>
+#include <stack>
+
+using namespace std;
+
+
+/// Mono Stack + DP
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    long long minCost(vector<int>& nums, vector<int>& costs) {
+
+        int n = nums.size();
+
+        vector<int> right_larger_or_equal(n, n);
+        vector<int> stack;
+        for(int i = n - 1; i >= 0; i --){
+            while(!stack.empty() && nums[i] > nums[stack.back()]) stack.pop_back();
+            if(!stack.empty()) right_larger_or_equal[i] = stack.back();
+            stack.push_back(i);
+        }
+//        for(int e: right_larger_or_equal) cout << e << ' '; cout << '\n';
+
+        vector<int> right_smaller(n, n);
+        stack.clear();
+        for(int i = n - 1; i >= 0; i --){
+            while(!stack.empty() && nums[i] <= nums[stack.back()]) stack.pop_back();
+            if(!stack.empty()) right_smaller[i] = stack.back();
+            stack.push_back(i);
+        }
+//        for(int e: right_smaller) cout << e << ' '; cout << '\n';
+
+        vector<long long> dp(n, LONG_LONG_MAX / 2);
+        dp[0] = 0;
+        for(int i = 0; i < n; i ++){
+            int to = right_larger_or_equal[i];
+            if(to < n)
+                dp[to] = min(dp[to], dp[i] + costs[to]);
+
+            to = right_smaller[i];
+            if(to < n)
+                dp[to] = min(dp[to], dp[i] + costs[to]);
+        }
+        return dp.back();
+    }
+};
+
+
+int main() {
+
+    vector<int> nums1 = {3, 2, 4, 4, 1}, costs1 = {3, 7, 6, 4, 2};
+    cout << Solution().minCost(nums1, costs1) << '\n';
+    // 8
+
+    vector<int> nums2 = {0, 1, 2}, costs2 = {1, 1, 1};
+    cout << Solution().minCost(nums2, costs2) << '\n';
+    // 2
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -2140,6 +2140,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 2294 | [Partition Array Such That Maximum Difference Is K](https://leetcode.com/problems/partition-array-such-that-maximum-difference-is-k/) | [无] | [C++](2001-2500/2294-Partition-Array-Such-That-Maximum-Difference-Is-K/cpp-2294/) | | |
 | 2295 | [Replace Elements in an Array](https://leetcode.com/problems/replace-elements-in-an-array/) | [无] | [C++](2001-2500/2295-Replace-Elements-in-an-Array/cpp-2295/) | | |
 | 2296 | [Design a Text Editor](https://leetcode.com/problems/design-a-text-editor/) | [无] | [C++](2001-2500/2296-Design-a-Text-Editor/cpp-2296/) | | |
+| 2297 | [Jump Game IX](https://leetcode.com/problems/jump-game-ix/) | [无] | [C++](2001-2500/2297-Jump-Game-IX/cpp-2297/) | | |
 | | | | | | |
 
 ## 力扣中文站比赛
