Computing một di chuyển tối đa

Question

thể trùng lặp:
Find the min number in all contiguous subarrays of size l of a array of size n

Tôi có một mảng (lớn) của dữ liệu số (kích thước N) và muốn tính toán một mảng chạy maximums với kích thước cửa sổ cố định w.

Trực tiếp hơn, tôi có thể xác định mảng mới out[k-w+1] = max{data[k-w+1,...,k]} cho k >= w-1 (điều này giả định mảng dựa trên 0, như trong C++).

Có cách nào tốt hơn để thực hiện việc này hơn N log(w) không?

[Tôi hy vọng sẽ có một tuyến tính tuyến tính trong N mà không phụ thuộc vào w, như cho trung bình di chuyển, nhưng không thể tìm thấy nó. Đối với N log(w) Tôi nghĩ rằng có một cách để quản lý với một cấu trúc dữ liệu được sắp xếp mà sẽ làm insert(), delete() và extract_max() hoàn toàn trong log(w) hoặc ít hơn cho một cấu trúc quy mô w - giống như một cây nhị phân được sắp xếp, ví dụ].

Cảm ơn bạn rất nhiều.

Answer 1

Có thực sự là một thuật toán có thể làm điều này trong thời gian O (N) không phụ thuộc vào kích thước cửa sổ w. Ý tưởng này là sử dụng một cấu trúc dữ liệu thông minh có hỗ trợ các hoạt động sau đây:

• Enqueue, có thêm một yếu tố mới để cấu trúc,
• Dequeue, mà loại bỏ các yếu tố lâu đời nhất từ ​​cấu trúc, và
• Tìm-tối đa, trả về (nhưng không xóa) phần tử tối thiểu khỏi cấu trúc.

Đây thực chất là cấu trúc dữ liệu hàng đợi hỗ trợ truy cập (nhưng không xóa) của phần tử tối đa. Thật ngạc nhiên, như đã thấy trong this earlier question, có thể triển khai cấu trúc dữ liệu này sao cho mỗi hoạt động này chạy trong thời gian O (1) được phân bổ. Kết quả là, nếu bạn sử dụng cấu trúc này để enqueue w yếu tố, sau đó liên tục dequeue và enqueue một yếu tố vào cấu trúc trong khi gọi find-max khi cần thiết, nó sẽ chỉ có O (n + Q) thời gian, trong đó Q là số các truy vấn bạn thực hiện. Nếu bạn chỉ quan tâm đến tối thiểu của mỗi cửa sổ một lần, điều này kết thúc là O (n), không phụ thuộc vào kích thước cửa sổ.

Hy vọng điều này sẽ hữu ích!

Answer 2

tôi sẽ chứng minh làm thế nào để làm điều đó với danh sách:

L = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 

với chiều dài N=23 và W = 4.

Làm hai bản sao mới của danh sách của bạn:

L1 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 
L2 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 

Vòng từ i=0 để N-1.Nếu i không chia hết cho số W, thì hãy thay thế L1[i] bằng max(L1[i],L1[i-1]).

L1 = [21, 21, 21, 21, | 3, 9, 11, 18, | 19, 19, 19, 23 | 20, 20, 20, 20 | 1, 2, 22, 22 | 8, 12, 12] 

Vòng từ i=N-2 to 0. Nếu i+1 không chia hết cho số W, thì hãy thay thế L2[i] bằng max(L2[i], L2[i+1]).

L2 = [21, 17, 16, 7 | 18, 18, 18, 18 | 23, 23, 23, 23 | 20, 15, 14, 14 | 22, 22, 22, 13 | 12, 12, 6] 

Lập một danh sách L3 chiều dài N + 1 - W, do đó L3[i] = max(L2[i], L1[i + W - 1])

L3 = [21, 17, 16, 11 | 18, 19, 19, 19 | 23, 23, 23, 23 | 20, 15, 14, 22 | 22, 22, 22, 13] 

Sau đó, danh sách này L3 là maxima di chuyển bạn tìm kiếm, L2[i] là tối đa phạm vi giữa i và tiếp theo đường thẳng đứng, trong khi l1[i + W - 1] là phạm vi tối đa của phạm vi giữa đường thẳng đứng và i + W - 1.