Google interview question: count bounded slices(min/max queue)

Question:

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).

 

直接的做法是对数组每个元素向右扫描，记录min/max，选择符合条件的slice作为结果，时间复杂度为O(N^2)。

我们发现对数组中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());
    }
}