2106. 摘水果 - Java 前缀和

原题地址：https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/

题解

时间复杂度击败37%，待优化

通过fruits数组，我们可以确立[0,frutis中最大坐标值]这个轴中各店的水果数量

建立起以startPos为中心的前缀和

• 当i<startPos时，prefix[i]为[i,startPos]的水果数量总和
• 当i>startPos时，prefix[i]为[startPos,i]的水果数量总和
• prefix[startPos]=startPos处的水果数量

我们可以将问题简化：

• 先向左走i步，然后向右走k-i步
  • 此时如果能够走到startPos右侧，我们在startPos左侧走了2i步，则一定有k-2i>0
  • 两次前缀和重复加了一次prefix[startPos]，所以需要减掉一次
  • 此时如果无法走到startPos右侧，则一定有k-2i<=0
• 先向右走i步，然后向左走k-i步
  • 此时如果能够走到startPos左侧，我们在startPos右侧走了2i步，则一定有k-2i>0
  • 同理需要减掉一次prefix[startPos]
  • 此时如果无法走到startPos左侧，则一定有k-2i<=0
• 对于i一定有i<=k

对于所有情况下的水果数量取最大值即可

时间复杂度：，建立map和前缀和各遍历一次数组，最后一次计算水果数量时循环k次

空间复杂度：

class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int maxLen=startPos;
        int max=Integer.MIN_VALUE;
        int[] map=new int[200001];
        for (int i=0;i<fruits.length;i++){
            maxLen=Math.max(maxLen,fruits[i][0]);
            map[fruits[i][0]]=fruits[i][1];
        }

        int[] prefix=new int[maxLen+1];
        prefix[startPos]=map[startPos];
        for(int i=startPos+1;i<prefix.length;i++){
            prefix[i]=prefix[i-1]+map[i];
        }
        for(int i=startPos-1;i>=0;i--){
            prefix[i]=prefix[i+1]+map[i];
        }

        for (int i=0;i<=k;i++){
            if(startPos+i<=maxLen){
                if((k-2*i)>0){
                    max=Math.max(max,prefix[startPos+i]+prefix[(startPos-(k-2*i)>=0)?startPos-(k-2*i):0]-prefix[startPos]);
                }else{
                    max=Math.max(max,prefix[startPos+i]);
                }
            }
            if(startPos-i>=0){
                if((k-2*i)>0){
                    max=Math.max(max,prefix[startPos-i]+prefix[(startPos+(k-2*i)<=maxLen)?startPos+(k-2*i):maxLen]-prefix[startPos]);
                }else{
                    max=Math.max(max,prefix[startPos-i]);
                }
            }
        }
        return max;
    }
}