diff options
Diffstat (limited to 'other/jump_game6.cpp')
-rw-r--r-- | other/jump_game6.cpp | 26 |
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); +} |