leetcode941：有效的山脉数组（valid-mountain-array）

[carloscn]

问题描述

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

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

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]

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/valid-mountain-array

[carloscn]

问题分析

使用数字进行遍历，一个从头开始遍历，一个从尾巴开始遍历：

• 从头遍历的分支，如果是涨的，那么继续遍历下一个，直到遍历出比其数据小的。记录坐标。

  • 如果出现相等的，则直接false
  • 如果遍历到最后都没有递减的数字，直接返回false

• 从尾巴遍历的分支，和从头遍历的规则是一致的。

• 如果两个分支记录的坐标不一致，则返回false，一致则返回true

pub fn valid_mountain_array(arr: Vec<i32>) -> bool
{
    let mut i:usize = 0;
    let mut a_pos:usize = 0;
    let mut b_pos:usize;

    if arr.len() < 3 {
        return false;
    }

    b_pos = arr.len() - 1;

    while i < arr.len() - 1 {
        if arr[i] == arr[i + 1] ||
           arr[arr.len() - i - 1] == arr[arr.len() - i - 2] {
            return false;
        }

        if (arr[i] > arr[i + 1]) && (0 == a_pos) {
            if (0 == i) && (0 == a_pos) {
                return false;
            }
            a_pos = i;
        }

        if (arr[arr.len() - i - 1] > arr[arr.len() - i - 2]) &&
           ((arr.len() - 1) == b_pos) {
            if (0 == i) && (arr.len() - 1 == b_pos) {
                return false;
            }
            b_pos = arr.len() - i - 1;
        }

        if a_pos != 0 && b_pos != (arr.len() - 1) && a_pos != b_pos {
            return false;
        }

        i += 1;
    }

    return true;
}

[carloscn]

code

https://github.com/carloscn/structstudy/commit/887a660d290aeb543fedd24fc9a58bbece45dab2 https://review.gerrithub.io/c/carloscn/structstudy/+/551934