【数组】941. 有效的山脉数组

[lyonyang]

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

arr.length >= 3
在 0 < i < arr.length - 1 条件下，存在 i 使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例 1：

输入：arr = [2,1]
输出：false

示例 2：

输入：arr = [3,5,5]
输出：false

示例 3：

输入：arr = [0,3,2,1]
输出：true

提示：

1 <= arr.length <= 104
0 <= arr[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[zhangke666163]

思路：

1. 遍历数组，找出最大的元素item
2. 遍历数组，左边元素递增且小于最大元素，右边元素递减小于最大元素
3. 用一个容器存储每一个元素是否满足条件的结果
   时间、空间复杂度：O(n)
   代码：

def is_mountain_array(array):
    max_item = array[0]
    if len(array) < 3:
        return False
    # 1. 找出最大元素
    for i in range(len(array)):
        if array[i] > max_item:
            max_item = array[i]
    if max_item in [array[0], array[-1]]:
        return False
    item_index = array.index(max_item)
    # 每个元素是否满足规则
    is_ok = []
    for i in range(len(array)-1):
        if i < item_index:
            # 左边元素
            if array[i] < array[i+1]:
                is_ok.append(True)
            else:
                is_ok.append(False)
            continue
        # 右边元素
        if i >= item_index:
            if array[i] > array[i+1]:
                is_ok.append(True)
            else:
                is_ok.append(False)
            continue
    if False in is_ok:
        return False
    else:
        return True
if __name__ == '__main__':
    print(is_mountain_array([1, 2, 3, 3, 1]))

[xuezc1119]

思路

递增判断并获取到目前为止的最大值
最大值后半段递减判断
第一个和最后一个都不能是最大值

复杂度

时间复杂度O(n)，空间复杂度O(1)

代码

/**
* @param {number[]} arr
* @return {boolean}
*/
var validMountainArray = function(arr) {
    if(arr && arr.length < 3) return false;
    let increase = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (increase < arr[i]) { // 递增
            increase = arr[i];
            if (i == arr.length-1) return false; // 只增不减
        } else { // 假定这个是最大值
            if (i == 1) return false; // 第一个大于第二个
            let data = arr.slice(i-1); // 截取后半段
            let decrease = data[0];
            for (let j = 1; j < data.length; j++) { // 后半段递减判断
                if (decrease <= data[j]) return false;
                decrease = data[j];
            }
            break;
        }
    }
    return true;
};

[lyonyang]

思路一 - 标志判断

定义一个标志位 , 标志是处于上升阶段还是下降阶段

注意 : 标志位最终结果必须标志着下降才是有效的山脉数组

# flag = 0 标志着处于上升阶段
# flag = 1 标志着处于下降阶段
class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        flag = 0
        for i in range(len(arr) - 1):
            if arr[i] == arr[i + 1]:
                return False
            # 上升
            if flag == 0:
                if arr[i] > arr[i + 1]:
                    if i == 0:
                        return False
                    flag = 1
            # 下降
            else:
                if arr[i] < arr[i + 1]:
                    return False
        if flag == 0:
            return False
        return True

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(1)$

思路二 - 双指针

利用双指针 , 分别同时从左右两边进行遍历 , 当左右指针都开始下降时停止 , 如果此时左右指针相等则为有效山脉 , 否则无效

注意 : 结束循环时 , 左指针不能是第一个元素 , 右指针不能是最后一个元素

class Solution:
    def validMountainArray(self, A) -> bool:
        if len(A) < 3: return False
        left, right = 0, len(A) - 1
        while left < right:
            # 左指针右移
            if A[left] < A[left + 1]:
                left += 1
                continue
            elif A[left] == A[left + 1]:
                return False
            # 右指针左移
            if A[right] < A[right - 1]:
                right -= 1
                continue
            elif A[right] == A[right - 1]:
                return False
            # 如果左有指针都不移动了就结束循环
            break
        if left == right and right != len(A) - 1 and left != 0:
            return True
        return False

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(1)$