java怎么实现非下降数组

# Java怎么实现非下降数组

## 目录
1. [什么是非下降数组](#什么是非下降数组)
2. [问题场景分析](#问题场景分析)
3. [基础实现方法](#基础实现方法)
   - [方法一：遍历检查](#方法一遍历检查)
   - [方法二：允许一次修改](#方法二允许一次修改)
4. [进阶优化方案](#进阶优化方案)
   - [贪心算法实现](#贪心算法实现)
   - [动态规划解法](#动态规划解法)
5. [边界条件处理](#边界条件处理)
6. [完整代码示例](#完整代码示例)
7. [性能对比](#性能对比)
8. [应用场景](#应用场景)
9. [总结](#总结)

## 什么是非下降数组

非下降数组（Non-decreasing Array）是指数组中每个元素都大于或等于前一个元素的数组。数学表达式为：

对于所有 1 ≤ i < n，满足 arr[i] ≥ arr[i-1]

示例：
- 合法数组：[1, 2, 2, 3, 5]
- 非法数组：[3, 2, 4, 1]

## 问题场景分析

实际开发中常见需求：
1. 数据验证：确保时间序列数据有序
2. 预处理步骤：为二分查找准备数据
3. 算法要求：如动态规划问题中的前提条件

典型LeetCode题目：
- [665. 非递减数列](https://leetcode.com/problems/non-decreasing-array/)

## 基础实现方法

### 方法一：遍历检查

```java
public boolean isNonDecreasing(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) {
            return false;
        }
    }
    return true;
}

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

方法二：允许一次修改

当允许修改最多一个元素时：

public boolean canBeNonDecreasing(int[] nums) {
    int count = 0;
    for (int i = 1; i < nums.length && count < 2; i++) {
        if (nums[i] < nums[i - 1]) {
            count++;
            if (i - 2 >= 0 && nums[i] < nums[i - 2]) {
                nums[i] = nums[i - 1];
            }
        }
    }
    return count <= 1;
}

处理逻辑： 1. 当发现逆序时，优先尝试修改前一个元素 2. 如果前前元素更大，则修改当前元素

进阶优化方案

贪心算法实现

public boolean checkPossibility(int[] nums) {
    int modifications = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) {
            if (modifications++ > 0) return false;
            if (i > 1 && nums[i] < nums[i - 2]) {
                nums[i] = nums[i - 1];
            }
        }
    }
    return true;
}

动态规划解法

计算最长非下降子序列长度：

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] >= nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return Arrays.stream(dp).max().getAsInt();
}

边界条件处理

需要特别注意的边界情况： 1. 空数组或单元素数组 2. 全部元素相同 3. 前两个元素逆序 4. 最后两个元素逆序

测试用例示例：

@Test
public void testEdgeCases() {
    assertTrue(checkPossibility(new int[]{1})); // 单元素
    assertTrue(checkPossibility(new int[]{1,1,1})); // 全等
    assertFalse(checkPossibility(new int[]{3,2,1})); // 完全逆序
    assertTrue(checkPossibility(new int[]{4,2,3})); // 可修复
}

完整代码示例

import java.util.Arrays;

public class NonDecreasingArray {
    
    // 基础检查版本
    public static boolean isNonDecreasing(int[] nums) {
        if (nums == null || nums.length == 0) return true;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return true;
    }
    
    // 允许修改一次的版本
    public static boolean checkPossibility(int[] nums) {
        if (nums == null) return false;
        if (nums.length <= 2) return true;
        
        int modifications = 0;
        for (int i = 1; i < nums.length && modifications <= 1; i++) {
            if (nums[i] < nums[i - 1]) {
                modifications++;
                if (i - 2 < 0 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        return modifications <= 1;
    }
    
    public static void main(String[] args) {
        int[] test1 = {4, 2, 3};
        System.out.println(checkPossibility(test1)); // true
        
        int[] test2 = {4, 2, 1};
        System.out.println(checkPossibility(test2)); // false
    }
}

性能对比

应用场景

1. 金融数据验证：确保股票价格时间序列数据有效
2. 游戏开发：检查关卡难度曲线设计是否合理
3. 物联网数据处理：传感器数据单调性验证
4. 数据库优化：为创建索引检查数据有序性

总结

1. 基础检查使用简单遍历即可实现
2. 允许修改的场景需要注意修改策略的选择
3. 动态规划解法虽然复杂度较高，但能提供更多信息
4. 实际开发中应根据具体需求选择合适方案

扩展思考： - 如何扩展到非上升数组？ - 如果允许k次修改该如何实现？ - 多维数组的非下降判断如何处理？ “`

注：本文实际字数约1600字，可通过以下方式扩展： 1. 增加更多代码注释 2. 添加复杂度分析的数学推导 3. 补充更多实际应用案例 4. 加入算法可视化图示