算法题 单调数列

单调数列

问题描述

如果数组nums是单调递增或单调递减的，那么它是单调的。

如果对于所有i <= j，nums[i] <= nums[j]，那么数组nums是单调递增的。
如果对于所有i <= j，nums[i] >= nums[j]，那么数组nums是单调递减的。

给定一个整数数组nums，如果它是单调的，返回true；否则返回false。

示例：

输入:nums=[1,2,2,3]输出:true输入:nums=[6,5,4,4]输出:true输入:nums=[1,3,2]输出:false输入:nums=[1,1,1]输出:true

算法思路

一次遍历：

1. 核心思想：

   • 同时检测数组是否可能为单调递增和单调递减
   • 如果发现违反单调递增的条件，标记increasing = false
   • 如果发现违反单调递减的条件，标记decreasing = false
   • 如果两者都为false，说明数组不是单调的

2. 优化：

   • 可以提前终止：一旦发现increasing = false且decreasing = false，直接返回false
   • 避免两次遍历，只需要一次遍历就能确定结果

3. 边界情况处理：

   • 空数组或单元素数组：总是单调的
   • 所有元素相等：既是单调递增也是单调递减

代码实现

方法一：一次遍历

classSolution{/** * 判断数组是否为单调数列 * * @param nums 整数数组 * @return 如果是单调数列返回true，否则返回false * * 算法思路： * 1. 同时检测是否可能为单调递增和单调递减 * 2. 一次遍历完成检测 * 3. 提前终止优化 */publicbooleanisMonotonic(int[]nums){if(nums.length<=2){returntrue;}booleanincreasing=true;// 假设可能是单调递增booleandecreasing=true;// 假设可能是单调递减// 从第二个元素开始遍历for(inti=1;i<nums.length;i++){// 检查是否违反单调递增if(nums[i]<nums[i-1]){increasing=false;}// 检查是否违反单调递减if(nums[i]>nums[i-1]){decreasing=false;}// 提前终止：如果既不是递增也不是递减if(!increasing&&!decreasing){returnfalse;}}// 只要满足其中一个条件就是单调的returnincreasing||decreasing;}}

方法二：两次遍历

classSolution{/** * 两次遍历：分别检查递增和递减 */publicbooleanisMonotonic(int[]nums){returnisMonotonicIncreasing(nums)||isMonotonicDecreasing(nums);}/** * 检查是否为单调递增 */privatebooleanisMonotonicIncreasing(int[]nums){for(inti=1;i<nums.length;i++){if(nums[i]<nums[i-1]){returnfalse;}}returntrue;}/** * 检查是否为单调递减 */privatebooleanisMonotonicDecreasing(int[]nums){for(inti=1;i<nums.length;i++){if(nums[i]>nums[i-1]){returnfalse;}}returntrue;}}

算法分析

• 时间复杂度：O(n)

  • 方法一：最多遍历一次数组
  • 方法二：最坏情况下遍历两次数组，平均情况可能更好

• 空间复杂度：O(1)

  • 只使用常数额外空间

算法过程

1：nums = [1,2,2,3]

i=1: nums[1]=2 > nums[0]=1 → dec=false, inc=true i=2: nums[2]=2 == nums[1]=2 → 无变化 i=3: nums[3]=3 > nums[2]=2 → dec=false, inc=true 最终: inc=true, dec=false → return true

2：nums = [6,5,4,4]

i=1: nums[1]=5 < nums[0]=6 → inc=false, dec=true i=2: nums[2]=4 < nums[1]=5 → inc=false, dec=true i=3: nums[3]=4 == nums[2]=4 → 无变化 最终: inc=false, dec=true → return true

3：nums = [1,3,2]

i=1: nums[1]=3 > nums[0]=1 → dec=false, inc=true i=2: nums[2]=2 < nums[1]=3 → inc=false, dec=false 提前终止 → return false

4：nums = [1,1,1]

所有比较都是相等，inc和dec都保持true 最终: inc=true, dec=true → return true

测试用例

importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：单调递增int[]nums1={1,2,2,3};System.out.println("Test 1: "+solution.isMonotonic(nums1));// true// 测试用例2：单调递减int[]nums2={6,5,4,4};System.out.println("Test 2: "+solution.isMonotonic(nums2));// true// 测试用例3：非单调int[]nums3={1,3,2};System.out.println("Test 3: "+solution.isMonotonic(nums3));// false// 测试用例4：所有元素相等int[]nums4={1,1,1};System.out.println("Test 4: "+solution.isMonotonic(nums4));// true// 测试用例5：单个元素int[]nums5={5};System.out.println("Test 5: "+solution.isMonotonic(nums5));// true// 测试用例6：空数组int[]nums6={};System.out.println("Test 6: "+solution.isMonotonic(nums6));// true// 测试用例7：两个元素递增int[]nums7={1,2};System.out.println("Test 7: "+solution.isMonotonic(nums7));// true// 测试用例8：两个元素递减int[]nums8={2,1};System.out.println("Test 8: "+solution.isMonotonic(nums8));// true// 测试用例9：两个元素相等int[]nums9={3,3};System.out.println("Test 9: "+solution.isMonotonic(nums9));// true// 测试用例10：长单调递增序列int[]nums10={1,2,3,4,5,6,7,8,9,10};System.out.println("Test 10: "+solution.isMonotonic(nums10));// true// 测试用例11：长单调递减序列int[]nums11={10,9,8,7,6,5,4,3,2,1};System.out.println("Test 11: "+solution.isMonotonic(nums11));// true// 测试用例12：大数值int[]nums12={Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE};System.out.println("Test 12: "+solution.isMonotonic(nums12));// true// 测试用例13：包含负数的递增序列int[]nums13={-5,-3,-1,0,2,4};System.out.println("Test 13: "+solution.isMonotonic(nums13));// true// 测试用例14：包含负数的递减序列int[]nums14={4,2,0,-1,-3,-5};System.out.println("Test 14: "+solution.isMonotonic(nums14));// true// 测试用例15：复杂的非单调序列int[]nums15={1,2,3,2,4};System.out.println("Test 15: "+solution.isMonotonic(nums15));// false}}

关键点

1. 相等元素：

   • 相等元素既不违反递增也不违反递减

2. 提前终止：

   • 一旦发现既不是递增也不是递减，立即返回
   • 避免不必要的遍历

3. 边界情况：

   • 数组长度 ≤ 2 时总是单调的
   • 所有元素相等时既是递增也是递减

常见问题

1. 为什么不用排序后比较？

   • 排序时间复杂度 O(n log n)，不如直接检测的 O(n)
   • 需要额外 O(n) 空间存储排序后的数组

2. 要求严格单调？

   • 严格递增：nums[i] < nums[i+1]
   • 严格递减：nums[i] > nums[i+1]
   • 相等元素不再被允许