Google interview question: count bounded slices(min/max queue) - dshao - 博客园
A Slice of an array said to be a Bounded slice if Max(SliceArray)-Min(SliceArray)<=K.
If Array [3,5,6,7,3] and K=2 provided .. the number of bounded slice is 9,
first slice (0,0) in the array Min(0,0)=3 Max(0,0)=3 Max-Min<=K result 0<=2 so it is bounded slice
second slice (0,1) in the array Min(0,1)=3 Max(0,1)=5 Max-Min<=K result 2<=2 so it is bounded slice
second slice (0,2) in the array Min(0,1)=3 Max(0,2)=6 Max-Min<=K result 3<=2 so it is not bounded slice
in this way you can find that there are nine bounded slice.
(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).
https://codility.com/programmers/task/count_bounded_slices
https://codility.com/media/train/solution-count-bounded-slices.pdf
http://www.cnblogs.com/dshao/p/4617563.html
Pair(int i1, int j1){i = i1; j = j1;}
return "("+i+"-"+j+")";
}
}
A Slice of an array said to be a Bounded slice if Max(SliceArray)-Min(SliceArray)<=K.
If Array [3,5,6,7,3] and K=2 provided .. the number of bounded slice is 9,
first slice (0,0) in the array Min(0,0)=3 Max(0,0)=3 Max-Min<=K result 0<=2 so it is bounded slice
second slice (0,1) in the array Min(0,1)=3 Max(0,1)=5 Max-Min<=K result 2<=2 so it is bounded slice
second slice (0,2) in the array Min(0,1)=3 Max(0,2)=6 Max-Min<=K result 3<=2 so it is not bounded slice
in this way you can find that there are nine bounded slice.
(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).
https://codility.com/programmers/task/count_bounded_slices
https://codility.com/media/train/solution-count-bounded-slices.pdf
http://www.cnblogs.com/dshao/p/4617563.html
我们发现对数组中index i的元素向右扫描到index j时不满足条件，那么以i为起点j之后的slice都不可能满足条件，因此需要右移i，相当于维护一个满足max-min<=k的滑动窗口。那么可以设计算法如下：(1) 创建一个min/max queue，要求push,pop,peek,getMax,getMin为常数时间。(2) 遍历数组，若当前元素不会导致队列内元素不满足条件时，push该元素；若当前元素会导致队列内元素不满足条件，则输出所有满足条件的结果（例如队列头index为2，当前index为5，则将(2,2),(2,3),(2,4)加入到结果中），pop队列头元素，再次检查当前元素能否入队列。这个算法的时间复杂度为O(N)。
那么如何实现我们所要求的min/max queue呢？我们知道只有队列头和队列尾是可以操作的（Java的Queue接口是LinkedList实现的，因此是可以用Iterator来遍历队列内部的元素，但若遍历队列求最大最小值，时间复杂度为O(N)）。实现min/max queue之前，我们先看一下如何实现min/max stack。
https://leetcode.com/problems/min-stack/
leetcode的这道题展示了如何构建min/max stack。我们需要构建一个额外堆栈来记录最大值，和一个额外的堆栈来记录最小值。
class MinMaxStack{ private Deque<Integer> stack = new LinkedList<>(); private Deque<Integer> minStack = new LinkedList<>(); private Deque<Integer> maxStack = new LinkedList<>(); public void push(int x) { stack.push(x); if(minStack.isEmpty() || minStack.peek()>=x) minStack.push(x); if(maxStack.isEmpty() || maxStack.peek()<=x) maxStack.push(x); } public int pop() { int tmp = stack.pop(); if(!minStack.isEmpty() && minStack.peek() == tmp) minStack.pop(); if(!maxStack.isEmpty() && maxStack.peek() == tmp) maxStack.pop(); return tmp; } public int peek() { return stack.peek(); } public boolean isEmpty(){ return stack.isEmpty(); } public int getMin() { if(!minStack.isEmpty()) return minStack.peek(); else return Integer.MAX_VALUE; } public int getMax(){ if(!maxStack.isEmpty()) return maxStack.peek(); else return Integer.MIN_VALUE; } }
利用min/max stack，我们可以构建min/max queue。如何用stack来模拟queue？我们用两个stack来实现queue的操作。当queue执行offer操作时，我们将这个元素push到stack 1中，当queue执行poll操作时，若stack 2为空，我们将所有stack 1中的元素pop-push到stack 2中，然后再从stack 2中pop。可以看到模拟queue的offer/poll操作的均摊时间复杂度为O(1)。我们知道queueMax=max(stack1Max, stack2Max), queueMin=min(stack1Min, stack2Min)。
class MinMaxQueue{ MinMaxStack stack1 = new MinMaxStack(); MinMaxStack stack2 = new MinMaxStack(); public void offer(int x){ stack1.push(x); } public int poll(){ if(!stack2.isEmpty()){ return stack2.pop(); } while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } return stack2.pop(); } public boolean isEmpty(){ return stack1.isEmpty() && stack2.isEmpty(); } public int getMin(){ return Math.min(stack1.getMin(), stack2.getMin()); } public int getMax(){ return Math.max(stack1.getMax(), stack2.getMax()); } }http://blueocean-penn.blogspot.com/2015/01/count-bounded-slices-using-minimum.html
Let's focus on find the minimum. Actually the problem essentially comes down to a data structure called minimum queue, which can find minimum value in the FIFO queue in O(1) time at any given time. To implement this kind of queue, we will use another data structure called minimum stack, which can find minimum value in the LIFO order in O(1) time. Combining a queue implementation with two stacks, we have our minimum queue implementation!
The take-home message of this problem is all of complicated coding problems are built on top of fundamentals like data structure (list, stack, queue, tree, hash) or search algorithms (binary search). There are thousands of hard coding problems, but there are only dozens or few hundreds of data structures and algorithms.
public static List<Pair> countSlices(int[] numbers, int k){
if(numbers==null)
return null;
List<Pair> list = new ArrayList<Pair>();
//p0, p1 defines the sliding windows
int p0=0, p1=0, len = numbers.length;
MQueue q = new MQueue();
q.enqueue(numbers[p1]);
while(p0<len && p1<len && p0<=p1){
int min = q.min();
int max = q.max();
if(max-min<=k){
for(int p=p1; p>=p0; p--){
list.add(new Pair(p1, p));
}
p1++;//expand sliding window
if(p1<len) q.enqueue(numbers[p1]);
}else{
p0++;//shrink sliding window
q.dequeue();
}
}
return list;
}
static class Pair{
int i; int j;Pair(int i1, int j1){i = i1; j = j1;}
@Override
public String toString(){return "("+i+"-"+j+")";
}
}
//a stack node which contains min and max of all underlying elements
static class MNode {
Integer i, min, max;
MNode(int i, int max, int min){this.i = i;this.max=max; this.min=min;}
}
//a stack(LIFO) can track min and max of all elements in amortized O(1) time
static class MStack {
Stack<MNode> s = new Stack<MNode>();
public boolean isEmpty(){
return s.isEmpty();
}
public int min(){
if(s.isEmpty())
return Integer.MAX_VALUE;
return s.peek().min;
}
public int max(){
if(s.isEmpty())
return Integer.MIN_VALUE;
return s.peek().max;
}
public void push(int i){
int max=Math.max(i, max());
int min=Math.min(i, min());
s.push(new MNode(i, max, min));
}
public int pop(){
return s.pop().i;
}
}
//a queue(FIFO) can track min and max of all elements in amortized O(1) time
static class MQueue{
MStack s_new = new MStack(), s_old = new MStack();
public void enqueue(int i){
s_new.push(i);
}
public int dequeue(){
if(s_old.isEmpty()){
while(!s_new.isEmpty()){
s_old.push(s_new.pop());
}
}
return s_old.pop();
}
public boolean isEmpty(){
return s_new.isEmpty() && s_old.isEmpty();
}
public int min(){
return Math.min(s_new.min(), s_old.min());
}
public int max(){
return Math.max(s_new.max(), s_old.max());
}
}
Slow solution O(N^2)
Fast solution O(N log N)
Notice that if the slice (i, j) is bounded then every slice (i + 1, j), (i + 2, j), . . . , (j, j) is
bounded too. There is no need to check index j from the beginning. Let’s assume there is a
minMaxQuery function, which returns the difference between maximum and minimum values
in a given slice.
Read full article from Google interview question: count bounded slices(min/max queue) - dshao - 博客园