剑指 Offer 59 - II. 队列的最大值

剑指 Offer 59 - II. 队列的最大值

思路

对于一个队列 :7 7 2 3 4 0 1 9

可以发现,在9出队列之前,2,3,4,0,1 这些数字对最大值没有贡献

对于队列:7 7 2 3 4

可以发现,在4出队列之前,2,3 这些数字对于最大子没有贡献

所以可以创建一个单调递减的队列,用于存放局部最大值

例如,对于4来说,单调队列最初是 7 7 3,4来了之后,发现只要4不出队列,3就不会对最大值有影响,所以3出队列即可

但是7会对最大值有影响,所以不能弹出7,把4压入队尾即可,等7弹出队列之后,最大值就变成4了。

TIPS

java中对于两个integer的比较如果是通过 == 符号,就会通过地址判断,两个对象是否相等

但是对于常量,例如:

Integer a = 3;
Integer b = 3;
if (a == b) {
    System.out.println("yes");
}

这份代码会输出yes

但是对于直接new一个对象,如下代码:

Integer integer1 = new Integer(13);
Integer integer2 = new Integer(13);
if (integer1 == integer2) {
    System.out.println(1);
}

就会判断不相等,如果用equals判断的话就是通过转为int的值进行判断的,就是相等的

Integer integer1 = new Integer(13);
Integer integer2 = new Integer(13);
if (integer1.equals(integer2)) {
    System.out.println(1);
}

假设通过 >= 进行两个integer的判断,应该也是通过值进行判断的,如下代码,就会判断是相等的

Integer integer1 = new Integer(13);
Integer integer2 = new Integer(13);
if (integer1 >=integer2) {
    System.out.println(1);
}

代码

class MaxQueue {
    private LinkedList<Integer> linkedList = new LinkedList<>();

    private LinkedList<Integer> maxList = new LinkedList<>();

    public void MaxQueue() {

    }

    public int max_value() {
        return maxList.isEmpty() ? -1 : maxList.peekFirst();
    }

    public void push_back(int value) {
        linkedList.addLast(value);
        while (!maxList.isEmpty() && value > maxList.peekLast()) {
            maxList.pollLast();
        }
        maxList.addLast(value);
    }

    public int pop_front() {
        if (linkedList.isEmpty()) {
            return -1;
        }
        Integer integer = linkedList.pollFirst();
        if (!maxList.isEmpty() && integer.equals(maxList.peekFirst())) {
            maxList.pollFirst();
        }
        return integer;
    }
}

上一篇:第六章 《子午线59》


下一篇:剑指 Offer 59 - II. 队列的最大值(单调队列)