Giá trị tối thiểu của các giá trị tối đa trong các phân đoạn phụ ... trong độ phức tạp O (n)

Question

Tôi đã phỏng vấn với Amazon cách đây vài ngày. Tôi không thể trả lời một trong những câu hỏi đã yêu cầu tôi hài lòng. Tôi đã cố gắng để có được câu trả lời sau cuộc phỏng vấn nhưng tôi đã không thành công cho đến nay. Đây là câu hỏi:

Bạn có một mảng các số nguyên có kích thước n. Bạn được cung cấp thông số k trong đó k < n. Đối với mỗi phân đoạn các phần tử liên tiếp có kích thước k trong mảng bạn cần để tính toán giá trị lớn nhất. Bạn chỉ cần trả lại giá trị tối thiểu của các giá trị tối đa này.

Ví dụ: 1 2 3 1 1 2 1 1 1 và k = 3 câu trả lời là 1.
Các phân đoạn sẽ là 1 2 3, 2 3 1, 3 1 1, 1 1 2, 1 2 1, 2 1 1, 1 1 1.
Giá trị tối đa trong mỗi phân đoạn là 3, 3, 3, 2, 2, 2, 1.
Giá trị tối thiểu của các giá trị này là 1 do đó câu trả lời là 1.

Câu trả lời hay nhất tôi đưa ra là độ phức tạp O (n log k). Những gì tôi làm là tạo một cây tìm kiếm nhị phân với các thành phần k đầu tiên, nhận giá trị tối đa trong cây và lưu nó trong biến minOfMax, sau đó lặp lại một phần tử tại một thời điểm với các phần tử còn lại trong mảng, xóa phần tử đầu tiên trong đoạn trước đó từ cây tìm kiếm nhị phân, chèn phần tử cuối cùng của phân đoạn mới vào cây, lấy phần tử tối đa trong cây và so sánh nó với minOfMax để lại trong minOfMax giá trị nhỏ nhất của hai.

Câu trả lời lý tưởng cần phải phức tạp O (n). Cảm ơn bạn.

Answer 1

Có một cách rất thông minh để thực hiện việc này liên quan đến this earlier question. Ý tưởng là có thể xây dựng một queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time (có nhiều cách để thực hiện việc này; hai cách được giải thích trong câu hỏi gốc). Khi bạn có cấu trúc dữ liệu này, hãy bắt đầu bằng cách thêm các phần tử k đầu tiên từ mảng vào hàng đợi trong thời gian O (k). Vì hàng đợi hỗ trợ O (1) find-max, bạn có thể tìm tối đa các phần tử k này trong thời gian O (1). Sau đó, liên tục dequeue một yếu tố từ hàng đợi và enqueue (trong O (1) thời gian) các yếu tố mảng tiếp theo. Sau đó bạn có thể truy vấn trong O (1) mức tối đa của mỗi phần tử con phần tử k này là gì. Nếu bạn theo dõi tối thiểu các giá trị này mà bạn thấy trong quá trình của mảng, thì bạn có một thuật toán O (n) -time, O (k) -space để tìm tối đa tối thiểu của các mảng con phần tử k.

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

Answer 2

câu trả lời của @ templatetypedef hoạt động, nhưng tôi nghĩ tôi có cách tiếp cận trực tiếp hơn.

Bắt đầu bằng cách tính toán tối đa cho các khoảng thời gian sau (khép kín):

[k-1, k-1] 
[k-2, k-1] 
[k-3, k-1] 
... 
[0, k-1] 

Lưu ý rằng mỗi người trong số này có thể được tính trong thời gian liên tục từ preceeding một.

Tiếp theo, tính toán tối đa cho những khoảng thời gian:

[k, k] 
[k, k+1] 
[k, k+2] 
... 
[k, 2k-1] 

Bây giờ những khoảng thời gian:

[2k-1, 2k-1] 
[2k-2, 2k-1] 
[2k-3, 2k-1] 
... 
[k+1, 2k-1] 

Tiếp theo bạn làm khoảng từ 2k 3k-1 ("chuyển khoảng"), sau đó từ 3k-1 xuống 2k + 1 ("khoảng lùi"). Và như vậy cho đến khi bạn đạt đến cuối mảng.

Đặt tất cả các thứ này vào một bảng lớn. Lưu ý rằng mỗi mục trong bảng này mất thời gian liên tục để tính toán. Quan sát rằng có tối đa 2 * n khoảng thời gian trong bảng (vì mỗi phần tử xuất hiện một lần ở bên phải của "khoảng thời gian chuyển tiếp" và một lần ở phía bên trái của "khoảng thời gian ngược").

Bây giờ, nếu [a, b] là bất kỳ khoảng thời gian rộng k, nó phải chứa chính xác một từ 0, k, 2k, ...

nói nó chứa m * k.

Quan sát các khoảng thời gian [a, m * k-1] và [m * k, b] đều ở đâu đó trong bảng của chúng tôi. Vì vậy, chúng tôi chỉ có thể tra cứu tối đa cho mỗi giá trị và giá trị tối đa của hai giá trị đó là giá trị cực đại của khoảng [a, b].

Vì vậy, đối với bất kỳ khoảng thời gian rộng nào k, chúng tôi có thể sử dụng bảng của chúng tôi để đạt được mức tối đa trong thời gian không đổi. Chúng ta có thể tạo bảng trong thời gian O (n). Kết quả sau.

Answer 3

Đây là triển khai (C#) của câu trả lời của templatetypedef.

public static void printKMax(int[] arr, int n, int k) 
    { 
     Deque<int> qi = new Deque<int>(); 
     int i; 
     for (i=0;i< k; i++) // first window of the array 
     { 
      while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()])) 
      { 
       qi.PopBack(); 
      } 
      qi.PushBack(i); 
     } 

     for(i=k ;i< n; ++i) 
     { 
      Console.WriteLine(arr[qi.PeekFront()]); // the front item is the largest element in previous window. 
      while (qi.Count > 0 && qi.PeekFront() <= i - k) // this is where the comparison is happening! 
      { 
       qi.PopFront(); //now it's out of its window k 
      } 
      while(qi.Count>0 && arr[i]>=arr[qi.PeekBack()]) // repeat 
      { 
       qi.PopBack(); 
      } 
      qi.PushBack(i); 
     } 

     Console.WriteLine(arr[qi.PeekFront()]); 
    }