algorithmzuo / coding-for-great-offer Goto Github PK

public int minAoeNums(int[] x, int[] hp, int range) {
    int ans = 0;
    int monsterNums = x.length;
    //当前攻击范围的左侧怪兽的下标
    int currentLeftI = 0;
    // 当前攻击范围的右侧怪兽下标
    int targetI = 0;
    //当前技能指向的怪兽下标
    int currentRightI = 0;
    //清空窗口内的怪兽,需要释放的技能次数
    int windowSum = 0;
    // hp窗口,记录某位置进入窗口后,要出窗口,作为最左侧未死亡怪兽时要承受的技能次数
    LinkedList<Integer> hpWindow = new LinkedList<>();
    // 对应hp窗口的怪兽坐标,用于获取下一个最左侧未死亡怪兽的坐标
    LinkedList<Integer> iWindow = new LinkedList<>();
    do {
        if (hpWindow.isEmpty()) {
            hpWindow.addLast(hp[currentLeftI]);
            iWindow.addLast(currentLeftI);
            windowSum += hp[currentLeftI];
            continue;
        }
        targetI = Math.max(currentLeftI, targetI) + 1;
        while (targetI < monsterNums && x[targetI] - x[currentLeftI] <= range) {
            // 假设要清空窗口中的怪物,targetI位置的怪物会被附带减伤windowSum的伤害
            int targetRestHp = hp[targetI] - windowSum;
            if (targetI > currentRightI && targetRestHp > 0) {
                hpWindow.addLast(targetRestHp);
                iWindow.addLast(targetI);
                windowSum += targetRestHp;
            }
            targetI++;
        }
        targetI--;
        currentRightI = Math.max(targetI, currentRightI) + 1;
        while (currentRightI < monsterNums && x[currentRightI] - x[targetI] <= range) {
            int rightRestHp = hp[currentRightI] - windowSum;
            if (rightRestHp > 0) {
                hpWindow.addLast(rightRestHp);
                iWindow.addLast(currentRightI);
                windowSum += rightRestHp;
            }
            currentRightI++;
        }
        // 快速结束,也可以去掉这个if判断
        if (currentRightI >= monsterNums) {
            ans += windowSum;
            return ans;
        }
        currentRightI--;
        // 施法范围的左侧怪兽死亡,结算需要释放的aoe次数
        if (!hpWindow.isEmpty()) {
            int leftMonsterDieHp = hpWindow.pollFirst();
            ans += leftMonsterDieHp;
            windowSum -= leftMonsterDieHp;
        }
        // 左侧怪兽下标调整,窗口为空,继续选择下一个怪兽,否则,从窗口中选择一个
        iWindow.pollFirst();
        if (iWindow.isEmpty()) {
            currentLeftI = currentRightI + 1;
        } else {
            currentLeftI = iWindow.peekFirst();
        }
    } while (currentLeftI < monsterNums);
    return ans;
}