Sliding Window Minimum

Problem

for (i = 0; i < ARR.size(); i++) {
  remove ARR[i-K] from the sliding window
  insert ARR[i] into the sliding window
  output the smallest value in the window
}

• ให้หา min(ARR[i] , ARR[i+1] , ARR[i+2] , ... , ARR[i+K-1])
• หรือ ถ้าอธิบายเป็นภาษาคนก็ คือ มีเลขอยู่ N ตัว ให้หาค่าน้อยที่สุด (min) ของตัวเลข K ตัวที่ติดกัน เช่น มีเลข 8 เลข ต้องการหาค่าน้อยสุดของเลข 3 ตัวที่อยู่ติดกัน (N=8, K=3)
• เช่น ARR = {1,2,5,8,6,2,4} , N=7 , K=3 , จะได้ เซตค่าน้อยสุดคิดเป็นช่วง 3 ตัวติดกัน = {1,1,1,2,5,2,2}

Complexity

• Naive Algorithms : O(NK) วิธีทื่อๆ
• Naive Algorithms : O(N log K) ถ้าใช้ heap มาช่วย
• Sliding Window Minimum : O(N) (ถ้าคิด Amortized O(1) per insertion/deletion กรณีใช้ Deque เข้ามาช่วย)

Sliding Window Minimum : O(N)

ไว้ว่างๆจะมาแปลต่อ = =" http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

2D-Array | Sliding Window Minimum : O(N^2)

วิธีแม่งโคตร เมพ บร๊ะเจ้าช่วย กล้วยทอด คนคิดช่างประเสริฐ โดยสัญชาติญาณ แท้ๆๆ เทียว ที เดียว เชียว http://stackoverflow.com/questions/10732841/sliding-window-minimum-maximum-in-2d