算法日常训练11.28（813.最大平均值和的分组）

 怎么看怎么不会，就想的到用回溯之类的，不过想都不用想，超时是肯定的，看一下答案，不就是动态规划的背包问题，以我的脑子确实想不到，还是老老实实学习别人的。

首先算出该数组的前缀和用于简化计算，sum[i]：前i个数的和，注意下标从1开始。

回溯三部曲：

定义dp：dp[i][k]：前i个数划分为k组的最大平均值和。注意下标都是从1开始的。

初始化dp：当k=1时，dp[i][1]=sum[i]/i;也就是只分一组，直接取他的平均值就是了。

状态转移公式：再定义一个j，j看作数组的断点，当k>1时，取dp[j][k-1]+avg(j,i)的最大值，这个值就是新的dp，也就是dp[i][n]=Math.max(dp[i][n],dp[j][n-1]+(sum[i]-sum[j])/(i-j))。

如果不好理解，想想背包问题，背包问题的dp[i][j]：前i个物品的总重量不超过j的最大值,是不是和这个题有异曲同工之处。

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int len=nums.length;
        double[] sum=new double[len+1];//前缀和
        double[][] dp=new double[len+1][k+1];//前i个数分为k组的最大平均值和
        for(int i=1;i<=len;i++){
            sum[i]=sum[i-1]+nums[i-1];
            dp[i][1]=sum[i]/i;//初始化，k=1时就是一个数组的平均值
        }
        
        for(int i=1;i<=len;i++){
            for(int n=2;n<=k;n++){
                for(int j=0;j
                    dp[i][n]=Math.max(dp[i][n],dp[j][n-1]+(sum[i]-sum[j])/(i-j));
                }
            }
        }
        return dp[len][k];
    }
    
}

 最简分数就代表分子分母的最大公约数为1，于是想到用gcd来写，两层循环，本来就想试试，没想到就过了。

class Solution {
    public List simplifiedFractions(int n) {
        List list=new ArrayList<>();
        for(int i=1;i//分子
            for(int j=i+1;j<=n;j++){//分母
                if(gcd(i,j)==1){
                    list.add(i+"/"+j);
                }
            }
        }
        return list;
    }
    public int gcd(int i,int j){
        return j>0?gcd(j,i%j):i;
    }
}

 第一反应是使用双指针，前面一个后面一个，当定位到坡度时就是一个最大宽度的坡度，但是双指针有致命的问题，就是不能确定什么时候前面的指针走什么时候后面的指针走，所以双指针是不能解决问题的。

这里采用单调栈的方法解决，维护一个单调递减的单调栈，再从后往前遍历数组，维护最大宽度。这里说明一下为什么栈里的数据可以弹出，首先要求的是最大宽度，当最后一个遍历完以后，比如倒数第二个数不比栈顶大，这是可以直接跳过的，因为要的是最大宽度，就算他比前面弹出的都大，他也没他后面的宽，这就是逆序遍历的原因。还有，比如6,5,7,4,3这样的，我们维护单调栈，怕不怕前面的数为7，而后面的数大于7，其实也是可以不用怕的，因为我们维护的是单调栈，到7时我们可以保证他前面有一个数比他小，那么有一个数大于他的话，显然他前面的数是更合理的答案。

class Solution {
    public int maxWidthRamp(int[] nums) {
         Stack stack=new Stack<>();
         for(int i=0;i//维护一个递减的单调栈
             if(stack.isEmpty()||nums[stack.peek()]>=nums[i])
             stack.push(i);
         }
         int res=0;
         for(int i=nums.length-1;i>=0;i--){
             while(!stack.isEmpty()&&nums[i]>=nums[stack.peek()]){
                 res=Math.max(res,i-stack.pop());
             }
         }
         return res;
    }
}