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. 加入算法可視化圖示