问题描述

小R所在的国家有n个城市，每个城市的人口为 a_i。如果某个城市的人口不超过其他任何一个城市人口的两倍，那么这个城市就被认为是稳定的。国家可以对部分城市实施政策，从而改变它们的人口数量。你的任务是帮助小R找到最少需要对多少个城市进行人口修改，才能使所有城市都变得稳定。

例如：对于城市人口为 [1, 2, 3, 4] 的国家，最少需要对1个城市执行政策，才能使所有城市稳定。

测试样例

样例1：

输入：n = 4 ,a = [1, 2, 3, 4]
输出：1

样例2：

输入：n = 5 ,a = [1, 10, 20, 30, 40]
输出：2

样例3：

输入：n = 3 ,a = [100, 50, 200]
输出：1

思路

每个城市的人口如果不超过其他城市人口的两倍，则这个城市是稳定的。换句话说，城市 i 的人口 a_i和城市j的人口a_j必须满足：

image-20241114105352891

我们需要找出最少修改多少个城市的人口，才能使所有城市都满足这个条件。

滑动窗口：通过滑动窗口（或者双指针方法）来找到最长的稳定子数组。最长稳定子数组中的城市不需要修改，因此最少修改的城市数是 n - 最大稳定子数组长度。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(n, a):
    # 1. 对人口数组进行排序
    a.sort()
    
    # 2. 使用滑动窗口法来找到最长稳定子数组
    left = 0  # 窗口的左边界
    max_stable_len = 0  # 最大稳定子数组的长度
    
    for right in range(n):
        # 检查当前窗口的稳定性，确保 a[right] <= 2 * a[left]
        while a[right] > 2 * a[left]:
            # 如果不稳定，窗口左边界右移，缩小窗口
            left += 1
        # 更新最大稳定子数组的长度
        max_stable_len = max(max_stable_len, right - left + 1)
    
    # 最少修改城市数是总城市数减去最大稳定子数组的长度
    return n - max_stable_len

# 测试样例
print(solution(4, [1, 2, 3, 4]))  # 输出：1
print(solution(5, [1, 10, 20, 30, 40]))  # 输出：2
print(solution(3, [100, 50, 200]))  # 输出：1