BM95 分糖果问题

题意

链接：分糖果问题_牛客题霸_牛客网 (nowcoder.com)

思路

题意可得

1. 极小值点只给一颗糖。
2. 如果左边都比右边小那么是个单调递增序列，且差值为1。如果左边都比右边大就可同理得。
3. 如果相等的话，只考虑不相等一边的情况，如果都相等则为1。
4. 将数组拆分一段又一段的单调序列话，就剩下一个极大值点需要讨论
5. 如果比左右两边都大，要同时满足左右两边的这点的糖果数就取决于左右两边谁需求的糖果数大了。

一开始我的思路，找单调递增和递减的长度，算一个等差数列，打算扫一遍算出来，但是后来想想好像情况有点复杂，总共有四种情况，比两边都大的点，即极大值点还要去遍历右边才能知道他的值，这样的话就是O(n^2),显然不行

优化方法就是从左往右和从左往右都扫一遍，每次只算一边的情况，然后取极大值。

具体步骤

1. 从左边开始扫，如果左边比他大，那么糖果数=左边糖果数+1，反之为1。糖果数组记为candyL
2. 从右边开始扫，如果右边比他大，那么糖果数=右边糖果数+1，反之为1。糖果数组记为candyR
3. 从左边开始累加max(candyL[i],candyR[i]),最后输出

代码如下

public int candy(int[] arr) {
       // write code here
       int ans = 0;
       int[] candyl=new int[arr.length+5];
       int[] candyr=new int[arr.length+5];
       int pre=arr[0];
       candyl[0]=1;
       candyr[arr.length-1]=1;
       for (int i = 1; i < arr.length; i++) {
           if(arr[i]>pre){
               candyl[i]=candyl[i-1]+1;
           }else {
               candyl[i]=1;
           }
           pre=arr[i];
       }
       pre=arr[arr.length-1];
       for (int i = arr.length-2; i >= 0; i--) {
           if(arr[i]>pre){
               candyr[i]=candyr[i+1]+1;
           }else {
               candyr[i]=1;
           }
           pre=arr[i];
       }
       for (int i=0;i<arr.length;i++){
           ans+=Math.max(candyl[i],candyr[i]);
       }
       return ans;
   }

算法全部代码参考leonyan18/AlgorithmCodeInJava (github.com)