x
信息
- 题目: 875.数组中的最长山脉
- 标签:
题解
解法1: 滑动窗口, 枚举山顶
Info
- 最小的山形状为
[a, b, c]\(a < b < c\) - 可以找到山顶, 然后向左右扩展检测
- 如果序列是 "上山"(严格递增), 那必然不是 "下山"(严格递减), 因此可以跳过前面已经判定的序列
pub fn longest_mountain(arr: Vec<i32>) -> i32 {
let mut ans = 0;
let mut cursor = 2; // 向后错位, 防止溢出
while cursor <= arr.len().checked_sub(1).unwrap_or(0) {
let (prev, curr, next) = (arr[cursor - 2], arr[cursor - 1], arr[cursor]);
if prev < curr && curr > next {
// 找到了山顶, 开始向两边扩展
let mut left = cursor;
while left > 1 && arr[left-2] < arr[left-1] {
left = left - 1; // 向左一格
}
let mut right = cursor;
while right < arr.len() && arr[right-1] > arr[right] {
right = right + 1; // 向右一格
}
let tmp = (cursor - left) + 1 + (right - cursor);
ans = ans.max(tmp);
cursor = right; // 下山的不会变上山, 因此可以跳过一点
continue;
}
cursor += 1;
}
ans as i32
}
解法2: 双指针, 枚举山脚
Info
- 不同于滑动窗口, 可以枚举山脚
- 假定左山脚, 然后向后扩展
- 扩展需要经历两个阶段, 先 上山 后 下山
- 同滑动窗口, 下山不会变上山, 因此可以跳过
pub fn longest_mountain(arr: Vec<i32>) -> i32 {
let n = arr.len();
let mut ans = 0;
let mut left = 0;
while left + 2 < n{
let mut right = left + 1;
// 假定自己在左边山脚
if arr[left] < arr[right]{
// 阶段1, 先上山
while right + 1 < n && arr[right] < arr[right+1]{
right += 1;
}
// 这时right在山顶
// 阶段2: 下山
if right + 1 < n && arr[right] > arr[right+1]{
while right + 1 < n && arr[right] > arr[right+1]{
right += 1;
}
ans = ans.max(right-left+1);
}
// 这时right在右山脚
}
// 已经检查过的, 不用再重复, 可以跳过
left = right;
}
ans as i32
}
解法3: DP, 记录 山路
Info
- 记录以当前节点为山顶时的 上山 和 下山 的山路长度
- 然后汇总两段山路, 得到最大组合
pub fn longest_mountain(arr: Vec<i32>) -> i32 {
if arr.len() < 3 {
return 0;
}
let mut lefts = vec![0; arr.len()];
for i in 1..arr.len() {
if arr[i - 1] < arr[i] {
lefts[i] = lefts[i - 1] + 1; // 上山路径加1
}
}
let mut rights = vec![0; arr.len()];
for i in (0..arr.len() - 1).rev() {
if arr[i] > arr[i + 1] {
rights[i] = rights[i + 1] + 1; // 下山路径加1
}
}
let mut ans = 0;
for i in 0..arr.len() {
if lefts[i] > 0 && rights[i] > 0 {
ans = ans.max(lefts[i] + rights[i] + 1);
}
}
ans
}
x