arrays - 最大化最小元素

Question

我们有一个包含 N 个正元素的数组。我们可以对这个数组进行 M 次操作。在每个操作中，我们必须选择一个长度为 W 的子数组(连续)并将每个元素增加 1。数组的每个元素最多可以增加 K 次。我们必须执行这些操作，以使数组中的最小元素最大化。

1 <= N, W <= 10^5

1 <= M, K <= 10^5

时间限制:1秒

我能想到一个 O(n^2) 的解决方案，但它超出了时间限制。有人可以为此提供 O(nlogn) 或更好的解决方案吗？

P.S.- 这是一道面试题

Answer 1

这是在谷歌面试中被问到的，我通过在范围逻辑中使用滑动窗口、堆和增量来解决它。我将分三部分解决问题:

1. 找出每个大​​小为 W 的子数组的最小值。这可以通过使用带有优先级队列的滑动窗口在 O(n) 中完成。每个窗口的最大值必须插入到具有 3 个变量的最小堆:[array_value, left_index, right_index]

2. 现在，将大小为 N 的辅助数组初始化为 0。在堆上执行 pop 操作 M 次，并且在每个 pop 操作中执行 3 个任务:

   value, left_index, right_index = heap.pop() #弹出最小值的理论函数

   将值增加 1，在 left_index 的辅助数组中递增 1，在 left_index 中递减 1right_index+1 处的辅助数组

   再次将这一对插入堆中。 [具有递增的值和相同的索引]

3. 执行 M 次操作后，用辅助数组遍历给定数组，并将累积和添加到索引 'i' 到数组中索引 'i' 处的元素。

返回数组的最小值。

时间复杂度

O(N) <- 每个窗口 + 构建堆中的最小元素。

O(M*logN) <- 提取并插入到堆中。

O(N) <- 用于遍历以添加累积和。

所以，总的来说是O(N + M*logN + N)，也就是O(M*logN)

空间复杂度

O(N) <- 额外的数组 + 堆。

上面很少有东西可以很容易地优化，比如在堆中插入值，只能插入 left_index 并且 right_index = left_index + k。

我的代码

from heapq import heappop, heappush
from collections import deque


def find_maximised_minimum(arr, n, m, k):

    """
    arr -> Array, n-> Size of array
    m -> increment operation that can be performed
    k -> window size
    """

    heap = []
    q = deque()
    # sliding window + heap building
    for i in range(k):
        while q and arr[q[-1]] > arr[i]:
            q.pop()
        q.append(i)

    for i in range(k, n):
        heappush(heap, [arr[q[0]], i - k, i - 1])
        while q and q[0] <= i - k:
            q.popleft()
        while q and arr[q[-1]] > arr[i]:
            q.pop()
        q.append(i)
    
    heappush(heap, [arr[q[0]], n - k, n - 1])

    # auxiliary array
    temp = [0 for i in range(n)]

    # performing M increment operations
    while m:
        top = heappop(heap)
        temp[top[1]] += 1
        try:
            temp[top[2] + 1] -= 1
        except:
            # when the index is last, so just ignore
            pass
        top[0] += 1
        heappush(heap, top)
        m -= 1

    # finding cumulative sum 
    sumi = 0
    for i in range(n):
        sumi += temp[i]
        arr[i] += sumi
    print(min(arr))


if __name__ == '__main__':
    # find([1, 2, 3, 4, 5, 6], 6, 5, 2)
    # find([73, 77, 60, 100, 94, 24, 31], 7, 9, 1)
    # find([24, 41, 100, 70, 97, 89, 38, 68, 41, 93], 10, 6, 5)
    # find([88, 36, 72, 72, 37, 76, 83, 18, 76, 54], 10, 4, 3)
    find_maximised_minimum([98, 97, 23, 13, 27, 100, 75, 42], 8, 5, 1)