'''
Description: 
Autor: Au3C2
Date: 2020-12-04 14:54:44
LastEditors: Au3C2
LastEditTime: 2020-12-04 14:58:00
'''
class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()
        n = len(stones)
        #最大值
        maxs = stones[n-1]-stones[0]+1-n- \
            min(stones[n-1]-stones[n-2]-1,stones[1]-stones[0]-1)
        #最小值
        mins = maxs
        tmp = 0
        for i in range(n):
            while stones[i]-stones[tmp]+1>n:
                tmp += 1
            cost = n-(i-tmp+1)
            if cost == 1 and \
                stones[i]-stones[tmp]+1 == n-1: # 左端致密情况
                mins = min(mins,2)
            else:
                mins = min(mins,cost) # 一般情况
        return [mins,maxs]

# 这题做得太久了，而且一开始没有往滑窗方向思考，tag还是很重要的。
# 我的策略也不是最优的，较优的答案参考：
# https://leetcode-cn.com/problems/moving-stones-until-consecutive-ii/solution/python3shuang-zhi-zhen-hua-dong-chuang-kou-by-gori/