package myJava ;
import java.util.ArrayDeque ;
class SlidingWindow {
int [ ] maxsDeque( int [ ] arr, int k) {
//Bounds check
if ( k > arr.length || k < 1 )
return new int [ ] { } ;
int windows = arr.length - k + 1 ; //number of windows
ArrayDeque< Integer> deck = new ArrayDeque< Integer> ( ) ;
int [ ] maximums = new int [ windows] ;
for ( int i = 0 ; i < arr.length ; i++ ) {
if ( i >= k )
maximums[ i- k] = arr[ deck.getFirst ( ) ] ;
while ( ! deck.isEmpty ( ) && arr[ i] >= arr[ deck.getLast ( ) ] )
deck.pollLast ( ) ;
while ( ! deck.isEmpty ( ) && deck.getFirst ( ) <= ( i- k) )
deck.pollFirst ( ) ;
deck.addLast ( i) ;
}
maximums[ windows- 1 ] = arr[ deck.getFirst ( ) ] ;
return maximums;
}
}
import static org.junit .Assert .*;
import org.junit.Before ;
import org.junit.BeforeClass ;
import org.junit.Test ;
public class SlidingWindowTest {
SlidingWindow win;
@Before
win = new SlidingWindow( ) ;
}
@Test
public void testMaxsDeque( ) {
assertArrayEquals(
new int [ ] { 11 ,6 ,6 ,9 ,9 ,9 ,8 ,15 } ,
win.maxsDeque ( new int [ ] { 11 , - 2 , 5 , 6 , 0 , 9 , 8 , - 1 , 2 , 15 } , 3 ) ) ;
assertArrayEquals(
new int [ ] { 6 ,6 ,9 ,9 ,9 ,8 ,15 } ,
win.maxsDeque ( new int [ ] { - 2 , 5 , 6 , 0 , 9 , 8 , - 1 , 2 , 15 } , 3 ) ) ;
assertArrayEquals(
new int [ ] { 500 } ,
win.maxsDeque ( new int [ ] { 500 } , 1 ) ) ;
assertArrayEquals(
new int [ ] { 6 ,6 ,6 } ,
win.maxsDeque ( new int [ ] { 6 ,6 ,6 } , 1 ) ) ;
assertArrayEquals(
new int [ ] { 6 } ,
win.maxsDeque ( new int [ ] { 6 ,6 ,6 } , 3 ) ) ;
assertArrayEquals(
new int [ ] { } ,
win.maxsDeque ( new int [ ] { 6 } , 2 ) ) ;
assertArrayEquals(
new int [ ] { } ,
win.maxsDeque ( new int [ ] { 6 } , 0 ) ) ;
}
}
cGFja2FnZSBteUphdmE7CgppbXBvcnQgamF2YS51dGlsLkFycmF5RGVxdWU7CgpjbGFzcyBTbGlkaW5nV2luZG93IHsKCglpbnRbXSBtYXhzRGVxdWUoaW50W10gYXJyLCBpbnQgaykgewoKCQkvL0JvdW5kcyBjaGVjawoJCWlmKCBrID4gYXJyLmxlbmd0aCB8fCBrIDwgMSkKCQkJcmV0dXJuIG5ldyBpbnRbXXt9OwoJCQoJCWludCB3aW5kb3dzID0gYXJyLmxlbmd0aCAtIGsgKyAxOyAvL251bWJlciBvZiB3aW5kb3dzCgoJCUFycmF5RGVxdWU8SW50ZWdlcj4gZGVjayA9IG5ldyBBcnJheURlcXVlPEludGVnZXI+KCk7CgkJaW50W10gbWF4aW11bXMgPSBuZXcgaW50W3dpbmRvd3NdOwoJCQoJCWZvciAoaW50IGkgPSAwOyBpIDwgYXJyLmxlbmd0aDsgaSsrKSB7CgkJCWlmKCBpID49IGsgKQoJCQkJbWF4aW11bXNbaS1rXSA9IGFycltkZWNrLmdldEZpcnN0KCldOwoJCQkKCQkJd2hpbGUgKCFkZWNrLmlzRW1wdHkoKSAmJiBhcnJbaV0gPj0gYXJyW2RlY2suZ2V0TGFzdCgpXSkKCQkJCWRlY2sucG9sbExhc3QoKTsKCQkJd2hpbGUgKCFkZWNrLmlzRW1wdHkoKSAmJiBkZWNrLmdldEZpcnN0KCkgPD0gKGktaykpCgkJCQlkZWNrLnBvbGxGaXJzdCgpOwoJCQlkZWNrLmFkZExhc3QoaSk7CgkJfQoJCW1heGltdW1zW3dpbmRvd3MtMV0gPSBhcnJbZGVjay5nZXRGaXJzdCgpXTsKCQlyZXR1cm4gbWF4aW11bXM7Cgl9Cgp9CgoKaW1wb3J0IHN0YXRpYyBvcmcuanVuaXQuQXNzZXJ0Lio7CmltcG9ydCBvcmcuanVuaXQuQmVmb3JlOwppbXBvcnQgb3JnLmp1bml0LkJlZm9yZUNsYXNzOwppbXBvcnQgb3JnLmp1bml0LlRlc3Q7CgpwdWJsaWMgY2xhc3MgU2xpZGluZ1dpbmRvd1Rlc3QgewoKCVNsaWRpbmdXaW5kb3cgd2luOwoKCUBCZWZvcmUKCXB1YmxpYyB2b2lkIHNldFVwKCkgdGhyb3dzIEV4Y2VwdGlvbiB7CgkJd2luID0gbmV3IFNsaWRpbmdXaW5kb3coKTsKCX0KCglAVGVzdAoJcHVibGljIHZvaWQgdGVzdE1heHNEZXF1ZSgpIHsKCQlhc3NlcnRBcnJheUVxdWFscygKCQkJCW5ldyBpbnRbXXsxMSw2LDYsOSw5LDksOCwxNX0sIAoJCQkJd2luLm1heHNEZXF1ZShuZXcgaW50W117IDExLCAtMiwgNSwgNiwgMCwgOSwgOCwgLTEsIDIsIDE1IH0sIDMpKTsJCQoJCQoJCWFzc2VydEFycmF5RXF1YWxzKAoJCQkJbmV3IGludFtdezYsNiw5LDksOSw4LDE1fSwgCgkJCQl3aW4ubWF4c0RlcXVlKG5ldyBpbnRbXXsgLTIsIDUsIDYsIDAsIDksIDgsIC0xLCAyLCAxNSB9LCAzKSk7CgkJCgkJYXNzZXJ0QXJyYXlFcXVhbHMoCgkJCQluZXcgaW50W117NTAwfSwgCgkJCQl3aW4ubWF4c0RlcXVlKG5ldyBpbnRbXXsgNTAwIH0sIDEpKTsJCgkJCgkJYXNzZXJ0QXJyYXlFcXVhbHMoCgkJCQluZXcgaW50W117Niw2LDZ9LCAKCQkJCXdpbi5tYXhzRGVxdWUobmV3IGludFtdeyA2LDYsNiB9LCAxKSk7CgkJYXNzZXJ0QXJyYXlFcXVhbHMoCgkJCQluZXcgaW50W117Nn0sIAoJCQkJd2luLm1heHNEZXF1ZShuZXcgaW50W117IDYsNiw2IH0sIDMpKTsKCQkKCQlhc3NlcnRBcnJheUVxdWFscygKCQkJCW5ldyBpbnRbXXt9LCAKCQkJCXdpbi5tYXhzRGVxdWUobmV3IGludFtdeyA2IH0sIDIpKTsKCQlhc3NlcnRBcnJheUVxdWFscygKCQkJCW5ldyBpbnRbXXt9LCAKCQkJCXdpbi5tYXhzRGVxdWUobmV3IGludFtdeyA2IH0sIDApKTsKCX0KCn0=