https://wiki.ta.in.th/index.php?action=history&feed=atom&title=Sliding_Window_Minimum 2026-06-16T22:57:20Z Revision history for this page on the wiki MediaWiki 1.33.0-alpha https://wiki.ta.in.th/index.php?title=Sliding_Window_Minimum&diff=93&oldid=prev 2019-03-07T17:13:45Z

<p>Created page with &quot;== Problem == for (i = 0; i &lt; ARR.size(); i++) { remove ARR[i-K] from the sliding window insert ARR[i] into the sliding window output the smallest value in the wind...&quot;</p> <p><b>New page</b></p><div>== Problem ==<br /> <br /> for (i = 0; i &lt; ARR.size(); i++) {<br /> remove ARR[i-K] from the sliding window<br /> insert ARR[i] into the sliding window<br /> output the smallest value in the window<br /> }<br /> * ให้หา min(ARR[i] , ARR[i+1] , ARR[i+2] , ... , ARR[i+K-1])<br /> * หรือ ถ้าอธิบายเป็นภาษาคนก็ คือ มีเลขอยู่ N ตัว ให้หาค่าน้อยที่สุด (min) ของตัวเลข K ตัวที่ติดกัน เช่น มีเลข 8 เลข ต้องการหาค่าน้อยสุดของเลข 3 ตัวที่อยู่ติดกัน (N=8, K=3)<br /> * เช่น ARR = {1,2,5,8,6,2,4} , N=7 , K=3 , จะได้ เซตค่าน้อยสุดคิดเป็นช่วง 3 ตัวติดกัน = {1,1,1,2,5,2,2}<br /> <br /> <br /> == Complexity ==<br /> <br /> * Naive Algorithms : '''O(NK)''' วิธีทื่อๆ<br /> * Naive Algorithms : '''O(N log K)''' ถ้าใช้ heap มาช่วย<br /> * Sliding Window Minimum : '''O(N)''' (ถ้าคิด Amortized O(1) per insertion/deletion กรณีใช้ Deque เข้ามาช่วย)<br /> <br /> <br /> == Sliding Window Minimum : O(N) ==<br /> ไว้ว่างๆจะมาแปลต่อ = =&quot;<br /> http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html<br /> <br /> == 2D-Array | Sliding Window Minimum : O(N^2) ==<br /> วิธีแม่งโคตร เมพ บร๊ะเจ้าช่วย กล้วยทอด คนคิดช่างประเสริฐ โดยสัญชาติญาณ แท้ๆๆ เทียว ที เดียว เชียว<br /> http://stackoverflow.com/questions/10732841/sliding-window-minimum-maximum-in-2d</div>

Tata