> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/hua-dong-chuang-kou/segment.md).

# 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

```