Segment

A company is performing an analysis on the computers at its main office. The computers are spaced along a single row. For each group of contiguous computers of a certain length, that is, for each segment, determine the minimum amount of disk space available on a computer. Return the maximum of these values as your answer.

Example

n = 4, the number of computers

space = [8, 2, 4, 6]

x = 2, the segment length

The free disk space of computers in each of the segments is [8, 2], [2, 4], [4, 6]. The minima of the three segments are [2, 2, 4]. The maximum of these is 4.

Function Description

Complete the function segment in the editor below.

segment has the following parameter(s):

int x:  the segment length to analyze

int space[n]:  the available hard disk space on each of the computers

Returns:

int: the maximum of the minimum values of available hard disk space found while analyzing the computers in segments of length x

Constraints

1 ≤ n ≤ 106

1 ≤ x ≤ n

1 ≤ space[i] ≤ 109

Input Format for Custom Testing Sample Case 0 Sample Input

STDIN Function

---

1 → length of segments x = 1 5 → size of space n = 5 1 → space = [1, 2, 3, 1, 2] 2 3 1 2

Sample Output

3

Explanation

The segments of size x = 1 are [1], [2], [3], [1], and [2]. Because each segment only contains 1 element, each value is minimal with respect to the segment it is in. The maximum of these values is 3.

Sample Case 1 Sample Case 2 Python 3 23242526272829303132333435363738394041424344454647484950515253545556575859606162

O(N*x)

(N-x)*x

if name == 'main': 19def segment(x, space): Line: 62 Col: 27

Input / Output

Test Cases

Console Input 1 5 1 2 3 1 2 Your Output (stdout) 3 Debug output 1 2 3 1

分析： sliding window+heapq, heapq无需保持x长度，只需要比较min不在范围时，去表头。

import heapq
def segment(x, space):
    if x >= len(space):
        return min(space)
    max_min = float('-inf')
    segs = []
    for i,e in enumerate(space):
        heapq.heappush(segs, (e,i))

        while segs[0][1] <= i - x:
            heapq.heappop(segs)
        if i >= x:
            max_min = max(max_min, segs[0][0])
    return max_min

space = [1]
x = 10000000000000
print(segment(x, space))

deque

remplate

// Some codefor right in range(len(nums)):
    # 加入右侧元素
    # 维护窗口（如加入到单调队列、哈希表等）
    
    if right >= k - 1:  # 只有窗口大小达到 k 时才开始处理
        # 计算当前窗口的答案（如最大值/最小值）
        
        # 维护窗口（移除左边元素，使窗口保持大小 k）

LeetCode 239. 滑动窗口最大值

from collections import deque

def segment(x, space):
    # Initialize a deque to store the indices of elements
    deq = deque()
    max_of_min = -float('inf')
    
    for i in range(len(space)):
        # Remove elements that are out of the current window
        if deq and deq[0] < i - x + 1:
            deq.popleft()

        # Remove elements from the deque that are larger than the current element
        while deq and space[deq[-1]] >= space[i]:
            deq.pop()

        # Add the current element's index to the deque
        deq.append(i)

        # If we have processed at least `x` elements, compute the minimum for the current window
        if i >= x - 1:
            max_of_min = max(max_of_min, space[deq[0]])

    return max_of_min