企业官网建设流程全解析

做去自己的网站,网站建设教程.,网站设计公司哪家好如何选择呀,wordpress注册邮箱配置单调数列 问题描述 如果数组 nums 是单调递增或单调递减的#xff0c;那么它是单调的。 如果对于所有 i j#xff0c;nums[i] nums[j]#xff0c;那么数组 nums 是单调递增的。 如果对于所有 i j#xff0c;nums[i] nums[j]#xff0c;那么数组 nums …单调数列问题描述如果数组nums是单调递增或单调递减的那么它是单调的。如果对于所有i jnums[i] nums[j]那么数组nums是单调递增的。如果对于所有i jnums[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.length2){returntrue;}booleanincreasingtrue;// 假设可能是单调递增booleandecreasingtrue;// 假设可能是单调递减// 从第二个元素开始遍历for(inti1;inums.length;i){// 检查是否违反单调递增if(nums[i]nums[i-1]){increasingfalse;}// 检查是否违反单调递减if(nums[i]nums[i-1]){decreasingfalse;}// 提前终止如果既不是递增也不是递减if(!increasing!decreasing){returnfalse;}}// 只要满足其中一个条件就是单调的returnincreasing||decreasing;}}方法二两次遍历classSolution{/** * 两次遍历分别检查递增和递减 */publicbooleanisMonotonic(int[]nums){returnisMonotonicIncreasing(nums)||isMonotonicDecreasing(nums);}/** * 检查是否为单调递增 */privatebooleanisMonotonicIncreasing(int[]nums){for(inti1;inums.length;i){if(nums[i]nums[i-1]){returnfalse;}}returntrue;}/** * 检查是否为单调递减 */privatebooleanisMonotonicDecreasing(int[]nums){for(inti1;inums.length;i){if(nums[i]nums[i-1]){returnfalse;}}returntrue;}}算法分析时间复杂度O(n)方法一最多遍历一次数组方法二最坏情况下遍历两次数组平均情况可能更好空间复杂度O(1)只使用常数额外空间算法过程1nums [1,2,2,3]i1: nums[1]2 nums[0]1 → decfalse, inctrue i2: nums[2]2 nums[1]2 → 无变化 i3: nums[3]3 nums[2]2 → decfalse, inctrue 最终: inctrue, decfalse → return true2nums [6,5,4,4]i1: nums[1]5 nums[0]6 → incfalse, dectrue i2: nums[2]4 nums[1]5 → incfalse, dectrue i3: nums[3]4 nums[2]4 → 无变化 最终: incfalse, dectrue → return true3nums [1,3,2]i1: nums[1]3 nums[0]1 → decfalse, inctrue i2: nums[2]2 nums[1]3 → incfalse, decfalse 提前终止 → return false4nums [1,1,1]所有比较都是相等inc和dec都保持true 最终: inctrue, dectrue → return true测试用例importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例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[i1]严格递减nums[i] nums[i1]相等元素不再被允许