牛客网真题-76-种花-美团MT47

贪心+暴力模拟，100%
由第一种方法可以产生一种递归方法，以最小点分割数组，递归两个子数组，递归只能过65%。
如下代码：注释中为贪心+模拟，
最佳思路：递增数组(评论区大佬)

package org.niuke.solution78;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int cnt = 0;

    public static void help(int[] arr, int minPre){
        if(arr.length <= 0){return;}
        if(arr.length == 1){
            cnt += arr[0]-minPre;
            return;
        }
        int min = Integer.MAX_VALUE, minIndex = 0;
        for(int i = 0; i < arr.length; i++){
            if(arr[i] < min){
                min = arr[i];
                minIndex = i;
            }
        }
        cnt += min - minPre;
        if(minIndex>0)help(Arrays.copyOfRange(arr, 0, minIndex), min);
        if(minIndex<arr.length-1)help(Arrays.copyOfRange(arr, minIndex + 1, arr.length), min);
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ints = new int[n];
        for(int i = 0; i < n; i++){
            ints[i] = scanner.nextInt();
        }
        //注释部分为暴力模拟
        //        int index = 0, cnt = 0;
        //        while (index < ints.length) {
        ////            System.out.println(Arrays.toString(ints));
        //            while (index < n && ints[index] == 0) {
        //                index++;
        //            }
        //            for(int i = index; i < n; i++){
        //                if(ints[i] == 0){
        //                    break;
        //                }else{
        //                    ints[i]--;
        //                }
        //            }
        //            if(index < n){
        //                cnt++;
        //            }
        //        }
        //        System.out.println(cnt);
        help(ints, 0);
        System.out.println(cnt);
    }
}