Keshawn_lu's Blog

Leetcode 845. 数组中的最长山脉

双指针 滑动窗口
字数统计: 550阅读时长: 2 min
2020/10/27 Share

题目简介：

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

  • B.length >= 3
  • 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

（注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉 ” 的长度。

如果不含有 “山脉 ” 则返回 0。

示例 1：

1
2
3
输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

示例 2：

1
2
3
输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000

思路：

利用滑动窗口的思路。

首先right只要满足right < A.size() && A[right] > A[right - 1]，便一直往右移动。若right一次也没有移动，则让left++, right = left + 1，直接continue即可。

否则再让right往右移动，需要满足的条件为right < A.size() && A[right] < A[right - 1]。若right一次也没有移动，则说明不满足要求，使新的左端点设为left = right即可（若这里right一次也没有移动，说明此时A[right] == A[right - 1]，因为前一个while停止循环时，说明A[right] <= A[right - 1]，所以使left = right即可）。

两次right都移动至少一次时，说明该区间符合要求，用res保存遍历过程中的最大区间长度。然后使新的左端点left = right - 1即可。

tip:

  • A.size() < 3时，直接返回0即可。
  • 需要注意while()条件里，边界条件需要写在最前面做限定。

代码如下：

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
class Solution {
public:
    int longestMountain(vector<int>& A) {

        if(A.size() < 3)
            return 0;

        int res = 0;

        int left = 0;
        int right = 1;

        int flag = 0;

        while(left < A.size() && right < A.size()){

            while(right < A.size() && A[right] > A[right - 1]){

                flag = 1;
                right++;
            }

            if(flag == 0){

                left++;
                right = left + 1;
                continue;
            }

            flag = 0;

            while(right < A.size() && A[right] < A[right - 1]){

                flag = 1;
                right++;
            }
            
            if(flag == 0){

                left = right;
                right = left + 1;
                continue;
            }
            
            res = max(res, right - left);

            left = right - 1;
            right = left + 1;

            flag = 0;
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网