AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

LeetCode 978. Longest Turbulent Subarray    原题链接    中等

作者: 作者的头像   wzc1995 ,  2019-01-21 01:25:55 ,  所有人可见 ,  阅读 1557


1


题目描述

一个 A 的子数组 A[i], A[i + 1], ..., A[j] 被称为是混乱的,当且仅当:

  • 对于 i <= k < j,当 k 为奇数时,A[k] > A[k+1] 成立,并且当 k 为偶数时,A[k] < A[k+1] 成立。
  • 或者,对于 i <= k < j,当 k 为偶数时,A[k] > A[k+1] 成立,并且当 k 为奇数时,A[k] < A[k+1] 成立。

即,如果比较符号在任何一组相邻的两个元素之间是反转的,则子数组是混乱的。

返回 A 最长混乱子数组的长度。

样例

输入:[9,4,2,10,7,8,8,1,9]
输出:5
解释:(A[1] > A[2] < A[3] > A[4] < A[5])
输入:[4,8,12,16]
输出:2
输入:[100]
输出:1

注意

  • 1 <= A.length <= 40000
  • 0 <= A[i] <= 10^9

算法

(贪心) $O(n)$
  1. 我们记录上一个相邻数对之间的比较符号。lastIndex 记录子数组的起始下标,lastSign 记录上一个数对之间的比较符号,初始时为 -1,表示任何比较符号都是合法的。
  2. 如果遍历时,发现当前数对的比较符号和上一个相同,则说明不符合规则。此时我们应该更新答案,然后将 lastIndex 设为 i - 1,比较符号不变。
  3. 如果发现当前数对两个数字相等,则需要更新答案,然后将 lastIndex 设为 i,比较符号设置为 -1。
  4. 如果满足规则,则继续遍历下一个数字。
  5. 最后,在返回答案前,还需要更新一次答案。

时间复杂度

  • 每个数字仅遍历一次,故总时间复杂度为 $O(n)$。

空间复杂度

  • 仅使用了常数的空间。

C++ 代码

class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int n = A.size(), ans = 1;
        int lastSign = -1, lastIndex = 0;
        for (int i = 1; i < n; i++) {
            if (A[i] == A[i - 1]) {
                ans = max(ans, i - lastIndex);
                lastIndex = i;
                lastSign = -1;
            }
            else {
                if (lastSign == -1) {
                    lastSign = (int)(A[i] > A[i - 1]);
                }
                else if (lastSign == (int)(A[i] > A[i - 1])) {
                    ans = max(ans, i - lastIndex);
                    lastIndex = i - 1;
                }
                else {
                    lastSign = 1 - lastSign;
                }
            }
        }
        ans = max(ans, n - lastIndex);
        return ans;
    }
};

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息