2022-10-19：一个数组如果满足 : 升降升降升降... 或者 降升降升... 都是满足的 给定一个数组， 1，看有几种方法能够剔除一个元素，达成上述的要求 2，数组天然符合要求返回 0 3，剔

use rand::Rng;use std::iter::repeat;fn main() {    let max_len: i32 = 10;    let max_value: i32 = 100;    let test_time: i32 = 30000;    println!("测试开始");    for _ in 0..test_time {        let len: i32 = rand::thread_rng().gen_range(0, max_len) + 1;        let mut arr = random_array(len, max_value);        let ans1 = ways1(&mut arr);        let ans2 = ways2(&mut arr);        if ans1 != ans2 {            println!("出错了!");            for num in &arr {                print!("{} ", num);            }            println!("");            println!("ans1 = {}", ans1);            println!("ans2 = {}", ans2);            break;        }    }    println!("测试结束");}
// 暴力方法// 为了验证fn ways1(arr: &mut Vec<i32>) -> i32 {    if is_wiggle(arr, -1) {        return 0;    }    let mut ans = 0;    for i in 0..arr.len() as i32 {        if is_wiggle(arr, i) {            ans += 1;        }    }    return if ans == 0 { -1 } else { ans };}
fn is_wiggle(arr: &mut Vec<i32>, remove_index: i32) -> bool {    let mut ans = true;    // 升    let mut request = true;    for i in 1..arr.len() as i32 {        if i == remove_index {            continue;        }        if i - 1 == remove_index && remove_index == 0 {            continue;        }        let last = if i - 1 == remove_index { i - 2 } else { i - 1 };        if request {            if arr[last as usize] >= arr[i as usize] {                ans = false;                break;            }        } else {            if arr[last as usize] <= arr[i as usize] {                ans = false;                break;            }        }        request = !request;    }    if ans {        return true;    }    ans = true;    // 降    request = false;    for i in 1..arr.len() as i32 {        if i == remove_index {            continue;        }        if i - 1 == remove_index && remove_index == 0 {            continue;        }        let last = if i - 1 == remove_index { i - 2 } else { i - 1 };        if request {            if arr[last as usize] >= arr[i as usize] {                ans = false;                break;            }        } else {            if arr[last as usize] <= arr[i as usize] {                ans = false;                break;            }        }        request = !request;    }    return ans;}
// 时间复杂度O(N)fn ways2(arr: &mut Vec<i32>) -> i32 {    if arr.len() < 2 {        return 0;    }    let n = arr.len() as i32;    let mut right_up: Vec<bool> = repeat(false).take(n as usize).collect();    let mut right_down: Vec<bool> = repeat(false).take(n as usize).collect();    right_up[(n - 1) as usize] = true;    right_down[(n - 1) as usize] = true;    let mut i = n - 2;    while i >= 0 {        right_up[i as usize] =            arr[i as usize] < arr[(i + 1) as usize] && right_down[(i + 1) as usize];        right_down[i as usize] =            arr[i as usize] > arr[(i + 1) as usize] && right_up[(i + 1) as usize];        i -= 1;    }    // 数组是不是天然符合！    if right_up[0] || right_down[0] {        return 0;    }    // 删掉0位置的数，数组达标还是不达标！    // 1 升    // 1 降    let mut ans = if right_up[1] || right_down[1] { 1 } else { 0 };    // ...[0]    let mut left_up = true;    let mut left_down = true;    let mut tmp;    let mut i = 1;    let mut l = 0;    let mut r = 2;    while i < n - 1 {        ans += if arr[l] > arr[r] && right_up[r] && left_down            || arr[l] < arr[r] && right_down[r] && left_up        {            1        } else {            0        };        // i（两个信息） i+1        // 变量复用        //      boolean curLeftUp = arr[l] > arr[i] && leftDown;        //      boolean curLeftDown =  arr[l] < arr[i] && leftUp;        //      leftUp = curLeftUp;        //      leftDown = curLeftDown;        tmp = left_up;        // 7 4        left_up = arr[l] > arr[i as usize] && left_down;        left_down = arr[l] < arr[i as usize] && tmp;        i += 1;        l += 1;        r += 1;    }    // 单独算一下 删掉n-1位置数的时候    ans += if left_up || left_down { 1 } else { 0 };    return if ans == 0 { -1 } else { ans };}
// 为了测试fn random_array(len: i32, max_value: i32) -> Vec<i32> {    let mut arr: Vec<i32> = vec![];    for _i in 0..len {        arr.push(rand::thread_rng().gen_range(0, max_value) + 1);    }    return arr;}