题目
假如有一群猫排成一行，要分配鱼干，每一只猫都有一个等级值。你作为管理员有很多鱼干但是需要按下边的分配制度分配：
1. 每一只猫至少要分配一斤鱼干，鱼干分配最小单位是斤，必须保证是整数。
2. 猫比他们邻居有更高等级值的分配的鱼干要多于他们的邻居。
为了满足上边的分配规则，需要得到需要的最少鱼干数量。
## 输入格式
第 1 行输入猫的数量 `N`
从第 2 行到第 `N + 1` 行，输入每一只猫的等级值 `D`。
## 输出格式
输出一个整数，表示需要的鱼干数量（斤）
**输入样例**
3
1
2
2**输出样例**
4
**数据范围**
1 <= `N` <= 10^3
1 <= `D` <= 10^6
解题思路
这题显然我们不能从头向后模拟，因为我们不确定后面的猫猫的等级，如果一点点向后推进模拟大概率得不到正确答案。
题目要求一个猫猫如果等级大于他旁边的猫猫，就要给它更多的鱼干，在这题中，我们要消耗最少的鱼干，所以只要给它（旁边等级低的猫的鱼干数量+1）个即可，这样来说等级高的猫猫获得的鱼干是由旁边的等级低的猫猫决定的，所以想要得到最小数量，我们就需要给等级低的猫猫最少的数量，假设三只猫的等级 为 1 2 3，我们给第一只1个鱼干，相应的第二只2个，第三只3个，这就是最少需要的鱼干。
由于存在等级差距，高等级的猫猫的鱼干是由低等级的猫猫的鱼干数决定的，所以我们从低等级的猫猫开始分配，找对最低等级的猫猫给它1个鱼干即可，然后按照等级依次判断，如果旁边没有比他的等级低的，给它分配一个鱼干即可
首先来看我自己设计的一个输入用例，一共八只猫🐱
模拟完成上述样例后可以得到以下规则：
如果当前猫猫的等级比两边的猫猫等级要高，则给它两只猫中较多的鱼干+1
如果当前猫猫等级大于左边猫猫等级，则给它左边猫猫鱼干+1
如果当前猫猫等级大于右边猫猫等级，则给它右边猫猫鱼干+1
否则，我们只需要给它一只鱼干即可（抠门的铲屎官）
思路有了，接下来就是具体代码实现的问题了
具体实现+代码
首先我们需要把每只猫猫所在的位置序号和等级绑定，存到二维数组中去，然后根据猫猫的等级从低到高排序，排序后按照以上规则依次判断即可。下面是实现代码
public static int solution(int n, List<Integer> catsLevels) {int[] catslevel = new int[n];//存储每只猫猫的等级int[] fishs = new int[n];//存储每只猫所分配的鱼干数int[][] cats = new int[n][2];// 存储猫猫下标和等级，将他们相绑定for (int i = 0; i < n; i++) {catslevel[i] = catsLevels.get(i);// 获取对应猫猫的等级cats[i][0] = i;//位置cats[i][1] = catslevel[i];//等级}Arrays.sort(cats, new Comparator<int[]>() {public int compare(int[] a, int[] b) {return a[1] - b[1];// 等级低的在前}});for (int[] x : cats) {int index = x[0], leftfish = 0, rightfish = 0;int leftlevel = 0, rightlevel = 0;if (index > 0) {leftfish = fishs[index - 1];leftlevel = catslevel[index - 1];}if (index < n - 1) {rightfish = fishs[index + 1];rightlevel = catslevel[index + 1];}//如果等级大于两边if (x[1] > leftlevel && x[1] > rightlevel) {fishs[index] = Math.max(leftfish, rightfish) + 1;} else if (x[1] > leftlevel) {//大于左边fishs[index] = leftfish + 1;} else if (x[1] > rightlevel) {//大于右边fishs[index] = rightfish + 1;} else//没有比他小的直接给1就行{fishs[index] = 1;}}int ans = 0;for(int x:fishs){ans+=x;}return ans;}
