最大磁盘空间的时间和空间复杂性

Question

from collections import deque
def findMax(hardDiskSpace, k):
    n = len(hardDiskSpace)
    if n * k == 0:
        return []
    if k > n:
        return []

    deq = deque()
    res = []
    i = 0
    while i < n:
        if deq and deq[0] == i - k:
            deq.popleft()
        while deq and hardDiskSpace[deq[-1]] > hardDiskSpace[i]:
            deq.pop()
        deq.append(i)

        if i >= k - 1:
            res.append(hardDiskSpace[deq[0]])
        i += 1
    print(res)
    print(max(res))


if __name__ == '__main__':
    hdd = [62, 64, 77, 75, 71, 60, 79, 75]
    k = 4
    findMax(hdd, k)

一家公司在其办公室的计算机上进行分析。计算机沿一排排列排列。分析的执行方式如下:从行的开头开始，选择一定数量计算机的一个连续段。分析每台计算机上可用的硬盘空间。确定此段中的最小可用磁盘空间。对第一个段执行这些步骤之后，将对下一个段重复这些步骤，继续此过程直到行的末尾(即，如果段大小为4，计算机1至4将被分析，然后2至5，等等)。给定此分析过程，编写一种算法，在分析过程中找到所有最小值中的最大可用磁盘空间。

输入

输入由三个参数组成：

numComputer：表示计算机数量的整数

hardDiskSpace：表示计算机硬盘空间的整数列表

segmentLength：是一个整数，表示在每次迭代中要考虑的计算机连续段的长度。

输出

返回一个整数，表示在分析过程中发现的所有最小值中的最大可用磁盘空间。

示例

输入

numComputer =3

hardDiskSpace = 62、64、77、75、71、60、79、75

segmentLength =4

产出: 64

请任何人解释一下上述问题的时间和空间复杂性。

Answer 1

列出的解在时间和空间上都是线性的(O(N))。它也不能比这更好，因为您至少需要阅读输入。

我将从空间复杂性开始，因为它更容易。

• ，您将获得大小N.
• 的列表输入，您将使用的唯一附加内存是保存当前最小值的deque及其可能的后继内存。segmentLength.
• There部件保证了这个队列永远不会比if deq and deq[0] == i - k: deq.popleft()更大--除了几个一次性变量之外，没有额外的空间。

因此空间复杂度为O(N).。

时间复杂度也是O(N)。让我们看看为什么：

• 外围while i < n:在整个计算机列表上迭代一次。指数i在每一步都会增加，因此我们不会有更长的停留时间的风险。外部循环though?
• Nothing的内部也错了:我们遍历的每个元素(hd空间)都被追加到队列中。
• 我们所遍历的每个元素在某个点被从队列中删除(除了那些更接近数组末尾的元素，而不是段大小)。这不会以任何方式改变结果)。因此，对于每一个元素，我们执行一次推送，或者一个弹出，或者一个弹出。pop、push和popleft都是在固定的时间内完成的但是，由于它只在队列为非空时执行pop，而且我们从未多次插入任何元素，所以没有问题。

我们应该首先使用的部分是corectness。不过，既然你没问，我就留到最后了：

核度的关键是我们用来求最小值的deque结构。最后的最大值(结果)只是完成触摸，因为最大值可以通过查看结果数组在线性时间内找到。

在每次迭代中，我们：

• 检查deque中最左边的索引是否过时。(如果最右边的索引元素小于当前索引元素，则不属于当前段anymore)
• Check的一部分)。如果是，我们就把它移除。重复，直到要么不再是真的，要么德克是空的。这保证了最左边的元素保持最小--如果不是的话，我们将在这个步骤中删除它。

，

• ，我们将新的添加插入到队列中。(因此队列包含一个非升序的minimum-candidates)
• If序列，我们已经加载了至少一个完整的段，我们将最左边的索引元素添加到结果集.

中。)

不确定这是否可以作为一个证据，然而，这是足够的理由，对我来说，确定它的工作。有趣的事实--我不得不重写这个部分，因为我采取了一种稍微不同的方法，当在解释的过程中不是这样的时候，我感到很困惑。

Answer 2

vector<int> minSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        int res=0;
        for (int i = 0; i < nums.size(); i++) {
            while (!dq.empty() and dq.front() <= i - k) dq.pop_front();
            while (!dq.empty() and nums[dq.back()] >=nums[i]) dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1) {
                 int x = nums[dq.front()];
                ans.push_back(x);
                res = max(res,x);
            }
        }
        return res;
    }