LeetCode 2498. 青蛙过河 II C#
原题链接
中等
作者:
hpstory
,
2022-12-13 15:36:47
,
所有人可见
,
阅读 265
C# 贪心 代码
public class Solution {
public int MaxJump(int[] stones) {
int n = stones.Length;
int result = stones[1] - stones[0];
for (int i = 2; i < n; i++){
result = Math.Max(result, stones[i] - stones[i - 2]);
}
return result;
}
}
C# 二分 代码
public class Solution {
private int[] stones;
public int MaxJump(int[] stones) {
int n = stones.Length;
this.stones = stones;
int left = 0, right = stones[n - 1];
while (left < right){
int mid = left + right >> 1;
if (Check(mid)) right = mid;
else left = mid + 1;
}
return left;
}
private bool Check(int x){
int n = stones.Length;
bool[] used = new bool[n];
for (int i = 0; i < n; i++){
int j = i + 1;
if (j < n && (stones[j] - stones[i]) > x) return false;
while (j < n && (stones[j] - stones[i]) <= x) j++;
used[j - 1] = true;
if (j == i + 1) j++;
i = j - 2;
}
used[0] = false;
for (int i = n - 1; i >= 0; i--){
int j = i - 1;
while (j >= 0 && used[j]) j--;
if (j >= 0 && (stones[i] - stones[j]) > x) return false;
if (j == i - 1) j--;
i = j + 2;
}
return true;
}
}