A.每日一题——3507. 移除最小数对使数组有序 I

题目链接：3507. 移除最小数对使数组有序 I（简单）

算法原理：

解法：模拟

3ms击败55.74%

时间复杂度O(N²)

由于数据范围非常小，所以直接按题意模拟即可

将nums的所有相邻元素全部扔进顺序表里，方便修改，在遍历顺序表的同时做三件事👇

①维护最小相邻数对和

②记录最小相邻数对和的第一个数出现的下标index

③判断nums是否满足非递减条件，如果不满足就更新

更新时，先将index置为新的最小和，然后删掉index+1位置的值

④重复以上操作，直至满足非递减条件或者只剩下一个数为止

Java代码：

class Solution { public int minimumPairRemoval(int[] nums) { List<Integer> list=new ArrayList<>(); for(int x:nums) list.add(x); int count=0; while(list.size()>1){ //默认满足非递减条件 boolean islegal=true; //维护最小和 int minsum=0x3f3f3f3f; //标记要修改的位置 int index=0; for(int i=0;i<list.size()-1;i++){ int sum=list.get(i)+list.get(i+1); //判断是否非递减 if(list.get(i)>list.get(i+1)) islegal=false; //更新最小和 if(sum<minsum){ minsum=sum; index=i; } } if(islegal) break; //没有break，说明还是非递减的状态，需要移除最小和 count++; list.set(index,minsum); list.remove(index+1); } return count; } }