LeetCode 1340. Jump Game V

题目链接

题意

给你一个arr,你可以选择从任意一个位置开始跳,每次跳的范围在[x-d,x+d],但是只能从高的往低的跳,问你跳的这个过程中最多经过几个位置?

思路

Top Down

首先第一个想法就是进行记忆化搜索,从每一个点i出发,按照规则分别往左和往右走,维护其最大值。但是由于状态多且有重复,因此可以采用记忆化搜索来减少搜索次数。
时间复杂度$O(n*d)$
空间复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
n = len(arr)
dp = [1] * n
def dfs(i):
if dp[i] != 1: return dp[i]
for dx in [-1, 1]:
for j in range(i + dx, i + d * dx + dx, dx):
if not (0 <= j < n and arr[j] < arr[i]): break
dp[i] = max(dp[i], dfs(j) + 1)
return dp[i]
return max(map(dfs, range(n)))

Bottom Up

另一种简单的想法来说就是: 每一个高位置的值都取决于每个比它低的,那么我们可以从最低的开始走,然后依次维护最大值即可。
时间复杂度$O(N\log N + N*D)$
空间复杂度$O(N)$

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
n = len(arr)
dp = [1] * n
for a, i in sorted([a, i] for i, a in enumerate(arr)):
for dx in [-1, 1]:
for j in range(i + dx, i + d * dx + dx, dx):
if not (0 <= j < n and arr[j] < arr[i]): break
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

线段树

延续上面的思想,我们从最低的位置开始,每个位置的值都已经处理好,那么对于当前的位置$i$,t它只能走一步,那么这个最大值肯定是往它左面所能走的区间和右面所能走的区间,其中一个的最大值。 区间最大值就可以用线段树来解决。
首先对于每个点我们需要获得它分别往左往右能达到的最大区间,这可以用单调栈$O(N)$来解决。然后我们从最低的位置开始,每次查询区间复杂度为$O(\log N)$,单点更新也是$O(\log N)$,因此:
时间复杂度$O(N\log N)$
空间复杂度$O(N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
private:
vector<int> tree;

public:
int query(int x, int l, int r, int ql, int qr){
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return tree[x];
int mid = l + r >> 1;
return max(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));
}
void update(int x, int l, int r, int pos, int val){
if (pos < l || pos > r) return ;
if (l == r) {
tree[x] = val;
return ;
}
int mid = l + r >> 1;
update(x << 1, l, mid, pos, val);
update(x << 1 | 1, mid + 1, r, pos, val);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
vector<int>bl(n), br(n);

stack<int> sta;
for (int i = 0; i < n; ++i){
while(!sta.empty() && arr[sta.top()] <= arr[i]){
br[sta.top()] = min(i - 1, sta.top() + d);
sta.pop();
}
sta.push(i);
}
while (!sta.empty())
{
br[sta.top()] = min(sta.top() + d, n - 1);
sta.pop();
}
for (int i = n - 1; i >= 0; --i){
while(!sta.empty() && arr[sta.top()] <= arr[i]){
bl[sta.top()] = max(i + 1, sta.top() - d);
sta.pop();
}
sta.push(i);
}
while(!sta.empty()){
bl[sta.top()] = max(0, sta.top() - d);
sta.pop();
}
vector<int>idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&] (int i, int j) {return arr[i] < arr[j];});
vector<int> ans(n);

tree.resize(4 * n + 4);

for (int id: idx){
int prev = 0;
if (bl[id] < id) prev = max(prev, query(1, 0, n - 1, bl[id], id - 1));
if (br[id] > id) prev = max(prev, query(1, 0, n - 1, id + 1, br[id]));
ans[id] = prev + 1;
update(1, 0, n - 1, id, ans[id]);
}
return *max_element(ans.begin(), ans.end());
}
};


-------------本文结束感谢您的阅读-------------


本文标题:LeetCode 1340. Jump Game V

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2020年02月05日 - 17:02

最后更新:2020年02月05日 - 17:02

原始链接:https://statusrank.xyz/articles/d480a368.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: