# 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

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/hua-dong-chuang-kou/segment.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.