最大化最小元素

Question

我们有一个由N个正整数组成的数组。我们可以在这个数组上执行M次操作。每次操作中，我们必须选择一个长度为W的子数组（连续的），并将每个元素增加1。数组中的每个元素最多可以增加K次。

我们必须执行这些操作，以使数组中的最小元素最大化。

限制条件如下： 1 <= N, W <= 10^5 1 <= M, K <= 10^5 时间限制：1秒

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

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

- Sumit Kumar

---

你的O(n^2)解决方案是什么？请在此发布，无论您认为它有多么琐碎。 - meowgoesthedog

你可能还想在另一个交流社区上咨询此问题：https://cstheory.stackexchange.com/ - Gian Marco Toso

达到-1秒的限制会非常困难，你试过用时间机器吗？也许你的意思是小于1秒，对吧？ - alseether

我们必须执行这些操作，以便将数组中的最小元素最大化。我已经多次阅读了这个内容，但仍然不确定它的确切含义。 - Component 10

@juandemarco 我觉得http://cs.stackexchange.com更适合。cstheory更多的是关于理论概念，而不是问题。 - Ivan Smirnov

Answer 1

这是谷歌面试中的一个问题，我使用滑动窗口、堆和区间增量来解决它。我将分为三个部分来解决这个问题:

1. 找出大小为W的每个子数组的最小值。可以使用带有优先队列的滑动窗口在O(n)时间内完成。每个窗口的最大值必须插入到一个min-heap中，具有3个变量: [array_value, left_index, right_index]

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

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

   将值加1， 在左索引处的辅助数组中增加1，在右索引+1处的辅助数组中减少1

   再次将此对插入堆中。[带有增加的值和相同的索引]

3. 执行M次操作后，使用辅助数组遍历给定的数组，并将累计总和添加到索引'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)

- learner-coder

---

仅供澄清，我不确定自己是否理解错误。当我们再次插入时，有可能相同的数字与其他窗口（leftIndex和rightIndex）一起出现在minHeap中。 - Nikhil Kumar vats

Answer 2

如果我们保留一个按升序排序的数组副本，将每个元素指向其原始索引，会怎样呢？考虑在增加元素时的优先顺序。此外，最终操作顺序是否重要？

一旦最低元素达到下一个最低元素，那么接下来必须增加什么？如果我们对任何一个元素应用了 k 次操作，那么这些增量是在哪个 w 中应用的，是否重要？

- גלעד ברקן