aboutsummaryrefslogtreecommitdiff
path: root/other/jump_game6.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/jump_game6.cpp')
-rw-r--r--other/jump_game6.cpp26
1 files changed, 26 insertions, 0 deletions
diff --git a/other/jump_game6.cpp b/other/jump_game6.cpp
new file mode 100644
index 0000000..81bbf05
--- /dev/null
+++ b/other/jump_game6.cpp
@@ -0,0 +1,26 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int maxResult(vector<int> &nums, int k) {
+ int ans = 0;
+ deque<int> dq;
+ for (int i = nums.size() - 1; i >= 0; i--) {
+ ans = nums[i] + (dq.empty() ? 0 : nums[dq.front()]);
+ while (!dq.empty() && ans > nums[dq.back()])
+ dq.pop_back();
+ dq.push_back(i);
+ if (dq.front() >= i + k)
+ dq.pop_front();
+ nums[i] = ans;
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> nums = {1, -1, -2, 4, -7, 3};
+ int k = 2;
+ cout << obj.maxResult(nums, k);
+}