算法题 单调数列
单调数列
问题描述
如果数组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算法思路
一次遍历：
核心思想：
- 同时检测数组是否可能为单调递增和单调递减
- 如果发现违反单调递增的条件，标记
increasing = false - 如果发现违反单调递减的条件，标记
decreasing = false - 如果两者都为
false，说明数组不是单调的
优化：
- 可以提前终止：一旦发现
increasing = false且decreasing = false，直接返回false - 避免两次遍历，只需要一次遍历就能确定结果
- 可以提前终止：一旦发现
边界情况处理：
- 空数组或单元素数组：总是单调的
- 所有元素相等：既是单调递增也是单调递减
代码实现
方法一：一次遍历
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 true2：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 true3：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 false4：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}}关键点
相等元素：
- 相等元素既不违反递增也不违反递减
提前终止：
- 一旦发现既不是递增也不是递减，立即返回
- 避免不必要的遍历
边界情况：
- 数组长度 ≤ 2 时总是单调的
- 所有元素相等时既是递增也是递减
常见问题
为什么不用排序后比较？
- 排序时间复杂度 O(n log n)，不如直接检测的 O(n)
- 需要额外 O(n) 空间存储排序后的数组
要求严格单调？
- 严格递增：
nums[i] < nums[i+1] - 严格递减：
nums[i] > nums[i+1] - 相等元素不再被允许
- 严格递增：