题目一：设计一个有getMin功能的栈

【题目】

​ 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

  1. pop、push、getMin操作的时间复杂度都是O(1).
  2. 设计的栈的类型可以使用现成的栈的结构。

【难度】

【解答】

​ 在设计时，我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和正常的栈没有头i与区别，这个栈记为stackData；另一个栈用来保存每一步的最小值，这个栈记为stackMin，具体的实现方式有两种。

第一种设计方案

  1. 压入数据规则

    假设当前数据为newNum，先将其压入stackData，然后判断stackMin是否为空：

    • 如果为空，则newNum压入stackMin.
    • 如果不为空，则比较newNum和stackMin中的元素哪个更小：
      • 如果newNum<=stackMin.pop()，则stackMin.push(newNum)
      • 如果newNum>stackMin.pop()，stackMin中不添加任何内容

  2. 弹出数据规则

    先在stackData中弹出栈顶元素，记为value。然后比较value和stackMin的栈顶元素的大小。根据压入栈的规则可知，stackMin.pop()既是stackData中最小的元素，也是stackMin中最小的元素。所以value和stackMin.pop()的大小关系只有下面两种：

    • value=stackMin.pop()：同时弹出stackData和stackMin的栈顶元素
    • value=stackMin.pop()：只弹出stackData的栈顶元素

  3. 查询当前栈中最小值的操作

    stackMin的栈顶元素中始终保存着stackData中的最小元素，所以minData=stackMin.pop()

方案一的代码实现如MyStack1类所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class MyStack1 {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    public MyStack1() {
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }
    
    public void push(int newNum) {
        if(this.stackMin.empty()) {
            this.stackMin.push(newNum);
        }else if (newNum <= this.getmin()) {
            this.stackMin.push(newNum)
        }
        this.stackData.push(newNum);
    }
    
    public int pop () {
        if (this.stackMin.empty){
            throw new RuntimeException("Your stack is empty.");
        }
        int value = stackData.pop();
        if (value == this.getmin()){
            this.stackMin.pop();
        }
        return value;
    }
    
    public int getmin () {
        if (this.stackMin.empty) {
            throw new RuntimeException("Your stack is empty.");
        }
        return this.stackMin.peek();
    }
}

第二种设计方案

  1. 压入数据规则

    假设当前数据为newNum，先将其压入stackData，然后判断stackMin是否为空：

    • 如果为空，则newNum压入stackMin.
    • 如果不为空，则比较newNum和stackMin中的元素哪个更小：
      • 如果newNum<=stackMin.pop()，则stackMin.push(newNum)
      • 如果newNum>stackMin.pop()，stackMin重复压入栈顶元素

  2. 弹出数据规则

    根据入栈规则，stackData和stackMin中的元素的个数是相同的，只需要将stackData中的栈顶元素弹出并赋值给value，stackMin中的栈顶元素弹出，返回value即可。

  3. 查询栈中的最小值

    同方案一中的查询当前栈中最小值的方法。return stackMin.peek();

【总结】

方案一和方案二的时间复杂度都是O(1); 空间复杂度都是O(n)。区别是方案一在入栈时稍省空间，在出栈时稍费空间，方案二在出栈时稍省空间，入栈时稍费空间。

题目二：由两个栈组成的队列

【题目】

​ 编写一个类，用两个栈实现队列，并支持队列的基本操作（add, poll, peek）。

​ 注：poll操作是出队操作，删除队列中的队首元素；peek操作获取队首元素的值不删除队首元素。

【难度】

【解答】

​ 我们可以将一个栈作为压入栈，在压入数据时，只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出，记为stackPop。

​ 因为在数据压入栈时顺序时先进后出的，那么只需要把stackPush的数据再压入stackPop栈中，顺序就变回来了。

​ 看似简单，实际上要注意两点：（1）如果stackPush要往stackPop中压入数据，那么必须要一次性把stackPush中的数据全部压入。（2）如果stackPop不为空，stackPush绝不能向stackPop中压入数据。

具体实现代码请参考TwoStacksQueue类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class TwoStacksQueue {
    public Stack<Integer> stackPush;
    public Stack<Integer> stackPop;

    public TwoStacksQueue() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }
    
    // stackPush栈向stackPop栈中倒入数据
    private void pushToPop() {
        if(stackPop.empty()){
            while(!stackPush.empty()){
                stackPop.push(stackPush.pop())
            }
        }
    }

    public void add(int pushInt) {
        stackPush.push(pushInt);
        pushToPop();
    }

    public int poll() {
        if(stackPop.empty() && stackPush.empty()){
            throw new RuntimeException("Queue is empty.");
        }
        pushToPop();
        return stackPop.pop();
    }

    public int peek() {
        if (stackPop.empty() && stackPush.empty()){
            throw new RuntimeException("Queue is empty.");
        }
        pushToPop();
        return stackPop.peek();
    }
}

【总结】

这种方法很巧妙，如果stackPop中为非空，那就没必要将stackPush中的元素倒入stackPop中，不需要实时地将stackPop中的元素导入stackPush中。

题目三：如何仅用递归函数和栈操作逆序一个栈

【题目】

一个栈依次压入 1、 2、 3、 4、 5， 那么从栈顶到栈底分别为 5、 4、 3、 2、 1。将这个栈转置后，从栈顶到栈底为 1、 2、 3、 4、 5，也就是实现栈中元素的逆序，但是只能用递归函数来实现， 不能用其他数据结构。

【难度】

【解答】

本题考察栈的操作和递归函数的设计，在这个题目中需要设计两个递归函数。

递归函数一：将stack的栈顶元素返回并移除

递归函数二：逆序一个栈，也就是题目中要求实现的方法

下面具体实现这两个递归调用：

递归函数一代码实现：

1
2
3
4
5
6
7
8
9
10
public static int getAndRemoveLastElement(Stack<Integer> stack) {
        int result = stack.pop();
        if(stack.isEmpty()){
            return result;
        }else {
            int last = getAndRemoveLastElement(stack);
            stack.push(result);
            return last;
    }
}

假设从stack的栈顶到栈底依次为3，2，1，这个函数的具体过程如下图所示：

递归函数二代码实现：

1
2
3
4
5
6
7
8
9
10
public static int getAndRemoveLastElement(Stack<Integer> stack) {
        int result = stack.pop();
        if(stack.isEmpty()){
            return result;
        }else {
            int last = getAndRemoveLastElement(stack);
            stack.push(result);
            return last;
    }
}

假设stack从栈顶到栈底依次为3，2，1，reverse函数的具体过程如下图所示：

【总结】

一遇到递归我就迷糊~

递归写的很巧妙，看书上的示意图我才看明白。

多记多练多总结吧，这本书看完，总结一个递归专题。

题目四：猫狗队列

【题目】

宠物、狗和猫的类如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Pet {
    private String type;
    
    public Pet(String type) {
        this.type = type;
    }
    
    public String getPetType() {
        return this.type;
    }
}

public class Dog extends Pet {
    public Dog() {
        super("dog");
    }
}

public class Cat extends Pet {
    public Cat() {
        super("cat");
    }
}

实现一个猫狗队列的结构，要求如下：

  • 用户可以调用 add 方法将 cat 类或 dog 类的实例放入队列中；
  • 用户可以调用 pollAll 方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
  • 用户可以调用 pollDog 方法，将队列中 dog 类的实例按照进队列的先后顺序依次弹出；
  • 用户可以调用 pollCat 方法，将队列中 cat 类的实例按照进队列的先后顺序依次弹出；
  • 用户可以调用 isEmpty 方法，检查队列中是否还有 dog 或 cat 的实例；
  • 用户可以调用 isDogEmpty 方法，检查队列中是否有 dog 类的实例；
  • 用户可以调用 isCatEmpty 方法，检查队列中是否有 cat 类的实例。

【难度】

【解答】

本题考察实现特殊数据结构的能力，以及针对特殊功能的算法设计能力。

书中作者给出了三种常见的错误：

  • cat 队列只放 cat 实例， dog 队列只放 dog 实例，再用一个总队列放所有的实例。
    错误原因： cat、 dog 以及总队列的更新问题。
  • 用哈希表， key 表示一个 cat 实例或 dog 实例， value 表示这个实例进队列的次序。
    错误原因：不能支持一个实例多次进队列的功能需求，因为哈希表的 key 只能对应一
    个 value 值。
  • 将用户原有的 cat 或 dog 类改写，加一个计数项来表示某一个实例进队列的时间。
    错误原因：不能擅自改变用户的类结构。

本题实现将不同的实例盖上时间戳的方法，但是又不能改变用户本身的类，所以定义一个新的类，具体的实现请参看下面的PetEnterQueue类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class PetEnterQueue {
    private Pet pet;
    private long count;

    public PetEnterQueue(Pet pet, long count) {
        this.pet = pet;
        this.count = count;
    }

    public Pet getPet() {
        return this.pet;
    }

    public long getCount() {
        return this.count;
    }

    public String getEnterPetType() {
        return this.pet.getType()
    }

}

在PetEnterQueue类中，count代表时间戳，pet代表原有的Pet实例，实际上PetEnterQueue类是在原有的类上进行一次封装。

要实现题目中的要求，大体来说，首先有个不断累加的数据项，用来表示实例进入队列的时间，同时有两个队列，一个只存放dog实例，另一个只存放cat实例，这两个队列分别用dogQ和catQ表示。要实现题目中的要求，大致可以描述如下：

  • 实现add方法：在加入实例时，首先生成一个PetEnterQueue实例，然后给这个实例加上时间戳，如果这个实例的类型是dog，就将这个实例放入到dogQ队列中，如果这个实例的类型时cat，就将这个实例放入到catQ中。
  • 实现pollAll方法：比较dogQ和catQ中实例的时间戳，谁早就先弹出谁
  • 实现pollDog方法：从dogQ中弹出即可
  • 实现pollCat方法：从catQ中弹出即可
  • 实现isEmpty方法：如果dogQ和catQ均为空则isEmpty方法返回True，否则返回False.
  • 实现isDogEmpty方法：如果dogQ为空则isDogEmpty方法返回True，否则返回False.
  • 实现isCatEmpty方法：如果catQ为空则isCatEmpty方法返回True，否则返回False.

DogCatQueue类的整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class DogCatQueue {
    private Queue<PetEnterQueue> dogQ;
    private Queue<PetEnterQueue> catQ;
    private long count;

    public DogCatQueue() {
        this.dogQ = new LinkedList<PetEnterQueue>();
        this.catQ = new LinkedList<PetEnterQueue>();
        this.count = 0;
    }

    public void add(Pet pet) {
        if (pet.getPetType().equals("dog")) {
            this.dogQ.add(new PetEnterQueue(pet, this.count++));
        } else if (pet.getPetType().equals("cat")) {
            this.catQ.add(new PetEnterQueue(pet, this.count++));
        } else {
            throw new RuntimeException("err, not dog or cat");
        }
    }

    public Pet pollAll() {
        if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
            if(this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
                return this.dogQ.poll().getPet();
            } else {
                return this.catQ.poll().getpet();
            }
        } else if (!this.dogQ.isEmpty()) {
            return this.dogQ.poll().getPet();
        } else if (!this.catQ.isEmpty()) {
            return this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("err, queue is empty.");
        }
    }

    public Dog pollDog() {
        if (!this.dogQ.isEmpty()) {
            return this.dogQ.poll().getPet();
        } else {
            throw new RuntimeException("err, Dog queue is empty.");
        }
    }

    public Cat pollCat() {
        if (!this.catQ.isEmpty()) {
            return this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("err, Cat queue is empty.");
        }
    }
    
    public boolean isEmpty() {
        return this.dogQ.isEmpty() && this.catQ.isEmpty();
    }

    public boolean isDogQueueEmpty() {
        return this.dogQ.isEmpty();
    }

    public boolean isCatQueueEmpty() {
        return this.catQ.isEmpty();
    }
}

题目五：用一个栈实现另一个栈的排序

【题目】

一个栈中的元素类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。 除此之外， 可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

【难度】

【解答】

将要排序的栈记为 stack，申请的辅助栈记为 help。在 stack 上执行 pop 操作，弹出的元素记为 cur。

  • 如果 cur 小于或等于 help 的栈顶元素，则将 cur 直接压入 help；
  • 如果 cur 大于 help 的栈顶元素，则将 help 的元素逐一弹出，逐一压入 stack，直到 cur 小于或等于 help 的栈顶元素，再将 cur 压入 help。

一直执行以上操作，直到 stack 中的全部元素都压入到 help。最后将 help 中的所有元素逐一压入 stack，即完成排序。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<Integer>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!help.isEmpty() && help.peek() < cur) {
                stack.push(help.ppop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
}

下面贴上自己写的垃圾代码，不能保证正确，只是想和书上的代码比较一下，我和标准答案差距有多大。差距也太大了┭┮﹏┭┮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<Integer>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            if (help.isEmpty) {
                help.push(cur);
            } else if (cur <= help.peek()) {
                help.push(cur);
            } else {
                while (cur > help.peek()) {
                    stack.push(help.pop());
                }
                help.push(cur);
            }
        }
        while (!help.isEmpty) {
            stack.push(help.pop());
        }
}

题目六：用栈来解决汉诺塔问题

略

题目七：生成窗口最大值数组

【题目】

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如， 数组为[4,3,5,4,3,3,6,7]，窗口大小为 3 时：
[4 3 5] 4 3 3 6 7 窗口中最大值为 5
4 [3 5 4] 3 3 6 7 窗口中最大值为 5
4 3 [5 4 3] 3 6 7 窗口中最大值为 5
4 3 5 [4 3 3] 6 7 窗口中最大值为 4
4 3 5 4 [3 3 6] 7 窗口中最大值为 6
4 3 5 4 3 [3 6 7] 窗口中最大值为 7
如果数组长度为 n，窗口大小为 w，则一共产生 n-w+1 个窗口的最大值。
请实现一个函数。

  • 输入：整型数组 arr，窗口大小为 w。
  • 输出：一个长度为 n-w+1 的数组 res， res[i]表示每一种窗口状态下的最大值。

以本题为例，结果应该返回{5,5,5,4,6,7}。

相关题目：LeetCode 第239题.滑动窗口最大值

【难度】

假设数组长度为 N，窗口大小为 w，如果做出时间复杂度为 O(N×w)的解法是不能让面试官满意的，本题要求面试者想出时间复杂度为 O(N)的实现。
本题的关键在于利用双端队列来实现窗口最大值的更新。首先生成双端队列 qmax， qmax 中存放数组 arr 中的下标。

从左到右依次遍历数组arr，假设遍历到arr[i]：

qmax 的放入规则为：

  1. 如果 qmax 为空，直接把下标 i 放进 qmax，放入过程结束
  2. 如果 qmax 不为空，取出当前 qmax 队尾存放的下标，假设为 j.
    • 如果 arr[j]>arr[i]，直接把下标 i 放入 qmax 的队尾，放入过程结束
    • 如果 arr[j]<=arr[i]，把 j 从 qmax 中弹出，重复 qmax 的放入规则

​ 也就是说，如果 qmax 是空的，就直接放入当前的位置。如果 qmax 不是空的， qmax 队尾的位置所代表的值如果不比当前的值大，将一直弹出队尾的位置，直到 qmax 队尾的位置所代表的值比当前的值大，当前的位置才放入 qmax 的队尾。

qmax 的弹出规则为：

​ 如果 qmax 队头的下标等于 i-w，说明当前 qmax 队头的下标已过期，弹出当前对头的下标即可。

在遍历数组的过程中，先将下标入队，然后再考虑是否弹出队首元素。

根据如上的放入和弹出规则， qmax 便成了一个维护窗口为 w 的子数组的最大值更新的结
构。 下面举例说明题目给出的例子。
1． 开始时 qmax 为空， qmax={}。
2． 遍历到 arr[0]=4，将下标 0 放入 qmax， qmax={0}。
3． 遍历到 arr[1]=3，当前 qmax 的队尾下标为 0，又有 arr[0]>arr[1]，所以将下标 1 放入 qmax 的尾部， qmax={0,1}。
4． 遍历到 arr[2]=5，当前 qmax 的队尾下标为 1，又有 arr[1]<=arr[2]，所以将下标 1 从 qmax 的尾部弹出， qmax 变为{0}。当前 qmax 的队尾下标为 0，又有 arr[0]<=arr[2]，所以将下标 0 从 qmax 尾部弹出， qmax 变为{}。将下标 2 放入 qmax， qmax={2}。此时已经遍历到下标 2 的位置，窗口 arr[0..2]出现，当前 qmax 队头的下标为 2，所以窗口 arr[0..2]的最大值为 arr[2]（即 5）。
5． 遍历到 arr[3]=4，当前 qmax 的队尾下标为 2，又有 arr[2]>arr[3]，所以将下标 3 放入 qmax 尾部， qmax={2,3}。窗口 arr[1..3]出现，当前qmax 队头的下标为 2，这个下标还没有过期，所以窗口 arr[1..3]的最大值为 arr[2]（即 5）。
6． 遍历到 arr[4]=3，当前 qmax 的队尾下标为 3，又有 arr[3]>arr[4]，所以将下标 4 放入 qmax 尾部， qmax={2,3,4}。窗口 arr[2..4]出现，当前 qmax 队头的下标为 2，这个下标还没有过期，所以窗口 arr[2..4]的最大值为 arr[2]（即 5）。
7． 遍历到 arr[5]=3，当前 qmax 的队尾下标为 4，又有 arr[4]<=arr[5]，所以将下标 4 从 qmax 的尾部弹出， qmax 变为{2,3}。当前 qmax 的队尾下标为 3，又有 arr[3]>arr[5]，所以将下标 5 放入 qmax 尾部， qmax={2,3,5}。窗口 arr[3..5]出现，当前 qmax 队头的下标为 2，这个下标已经过期，所以从 qmax 的头部弹出， qmax 变为{3,5}。当前 qmax 队头的下标为 3，这个下标没有过期，所以窗口 arr[3..5]的最大值为 arr[3]（即 4）。
8． 遍历到 arr[6]=6，当前 qmax 的队尾下标为 5， 又有 arr[5]<=arr[6]，所以将下标 5 从 qmax 的尾部弹出， qmax 变为{3}。当前 qmax 的队尾下标为 3，又有 arr[3]<=arr[6]，所以将下标 3 从 qmax 的尾部弹出， qmax 变为{}。将下标 6 放入 qmax， qmax={6}。窗口 arr[4..6]出现，当前qmax 队头的下标为 6，这个下标没有过期，所以窗口 arr[4..6]的最大值为 arr[6]（即 6）。
9． 遍历到 arr[7]=7，当前 qmax 的队尾下标为 6，又有 arr[6]<=arr[7]，所以将下标 6 从 qmax 的尾部弹出， qmax 变为{}。将下标 7 放入 qmax， qmax={7}。窗口 arr[5..7]出现，当前 qmax 队头的下标为 7，这个下标没有过期，所以窗口 arr[5..7]的最大值为 arr[7]（ 即 7）。
10． 依次出现的窗口最大值为[5,5,5,4,6,7]，在遍历过程中收集起来，最后返回即可。上述过程中，每个下标值最多进 qmax 一次，出 qmax 一次。所以遍历的过程中进出双端队列的操作是时间复杂度为 O(N)，整体的时间复杂度也为 O(N)。

具体过程参看如下代码中的 getMaxWindow 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] getMaxWindow(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    LinkedList<Integer> qmax = new LinkedList<Integer>();
    int[] res = new int[arr.length - w + 1];
    int index = 0;
    for (int i = 0; i < arr.length; i++) {
        // 插入队列
        while (!qmax.isEmpty() && arr[i] >= arr[qmax.peekLast()]) {
            qmax.pollLast();
        }
        qmax.addLast(i);
        // 弹出
        if (qmax.peekFirst() == i - w) {
            qmax.pollFirst();
        }
        if (i >= w - 1) {
            res[index++] = arr[qmax.peekFirst()];
        }
    }
    return res;
}

题目八：单调栈结构

【题目】

​ 给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i]小的位置。返回所有位置相应的信息。

相关题目：leetcode第496题.下一个更大元素Ⅰ

【举例】
arr = {3,4,1,5,6,2,7}

返回如下二维数组作为结果：

{
{-1, 2},
{ 0, 2},
{-1,-1},
{ 2, 5},
{ 3, 5},
{ 2,-1},
{ 5,-1}
}

​ -1表示不存在。所以上面的结果表示在 arr 中， 0 位置左边和右边离 0 位置最近且值比 arr[0]小的位置是-1 和 2； 1 位置左边和右边离 1 位置最近且值比 arr[1]小的位置是 0 和 2； 2 位置左边和右边离 2 位置最近且值比 arr[2]小的位置是-1 和-1……

进阶问题： 给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i]小的位置。返回所有位置相应的信息。

【要求】

​ 如果 arr 长度为 N，实现原问题和进阶问题的解法，时间复杂度都达到 O(N)。

【难度】

【解答】

本题实现时间复杂度为 O($N^2$)的解是非常容易的，每个位置分别向左和向右遍历一下，就可以确定答案。下面给出该方法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[][] rightWay(int[] arr) {
    int[][] res = new int[arr.length][2];
    for (int i = 0; i < arr.length; i++) {
        int leftLessIndex = -1;
        int rightLessIndex = -1;
        int cur = i - 1;
        while (cur >= 0) {
            if (arr[cur] < arr[i]) {
                leftLessIndex = cur;
                break;
            }
            cur--;
        }
        cur = i + 1;
        while (cur < arr.length) {
            if (arr[cur] < arr[i]) {
                rightLessIndex = cur;
                break;
            }
            cur++;
        }
        res[i][0] = leftLessIndex;
        res[i][1] = rightLessIndex;
    }
    return res;
}

​ 关键在于生成所有位置的相应信息，时间复杂度做到 O(N)，这需要用到单调栈结构，这个结构在算法面试中经常出现，本章还用单调栈结构解决了几个问题，请读者好好掌握这种结构。

​ 首先解决原问题，也就是没有重复值的数组如何使用单调栈解决这个问题，然后看看可能含有重复值的数组如何使用单调栈。
​ 原问题： 准备一个栈， 记为 stack<Integer>，栈中放的元素是数组的位置，开始时 stack 为空。如果找到每一个 i 位置左边和右边离 i 位置最近且值比arr[i]小的位置，那么需要让 stack 从栈顶到栈底的位置所代表的值是严格递减的；如果找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i]大的位置，那么需要让 stack 从栈顶到栈底的位置所代表的值是严格递增的。本题需要解决的是前者，但是对于后者，原理完全是一样的。

​ 下面用例子来展示单调栈的使用和求解流程，初始时 arr = {3,4,1,5,6,2,7}， stack 从栈顶到栈底为： {}；

​ 遍历到 arr[0]=3，发现 stack 为空，就直接放入 0 位置。 stack 从栈顶到栈底为： {0 位置(值是 3)}；

​ 遍历到 arr[1]=4，发现直接放入 1 位置，不会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。 stack 从栈顶到栈底依次为： {1 位置(值是 4)、 0 位置(值是 3)}；

​ 遍历到 arr[2]=1，发现直接放入 2 位置（值是 1），会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，所以从 stack 开始弹出位置。如果 x 位置被弹出，在栈中位于 x 位置下面的位置，就是 x 位置左边离 x 位置最近且值比 arr[x]小的位置；当前遍历到的位置就是 x 位置右边离 x 位置最近且值比 arr[x]小的位置。从 stack 弹出位置 1，在栈中位于 1 位置下面的是位置 0，当前遍历到的是位置 2，所以 ans[1]={0,2}。弹出 1 位置之后，发现放入 2 位置（值是 1） 还会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，所以继续弹出位置 0。在栈中位于位置 0 下面已经没有位置了，说明在位置 0 左边不存在比 arr[0]小的值，当前遍历到的是位置 2，所以 ans[0]={-1,2}。 stack 已经为空， 所以放入 2 位置（值是 1）， stack 从栈顶到栈底为： {2 位置(值是 1)}；

​ 遍历到 arr[3]=5，发现直接放入 3 位置，不会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack 从栈顶到栈底依次为：{3 位置(值是 5)、2 位置(值是 1)}；

​ 遍历到 arr[4]=6，发现直接放入 4 位置，不会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack 从栈顶到栈底依次为：{4 位置(值是 6)、3 位置(值是 5)、2位置(值是 1)}；

​ 遍历到 arr[5]=2，发现直接放入 5 位置，会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，所以开始弹出位置。弹出位置 4，栈中它的下面是位置 3，当前是位置 5，ans[4]={3,5}。弹出位置 3，栈中它的下面是位置 2，当前是位置 5，ans[3]={2,5}。然后放入 5 位置就不会破坏stack 的单调性了。stack 从栈顶到栈底依次为：{5 位置(值是 2)、2 位置(值是 1)}；

​ 遍历到 arr[6]=7，发现直接放入 6 位置，不会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack 从栈顶到栈底依次为：{6 位置(值是 7)、5 位置(值是 2)、2位置(值是 1)}。

​ 遍历阶段结束后，清算栈中剩下的位置。
​ 弹出 6 位置，栈中它的下面是位置 5，6 位置是清算阶段弹出的，所以 ans[6]={5,-1}；
​ 弹出 5 位置，栈中它的下面是位置 2，5 位置是清算阶段弹出的，所以 ans[5]={2,-1}；
​ 弹出 2 位置，栈中它的下面没有位置了，2 位置是清算阶段弹出的，所以 ans[2]={-1,-1}。

​ 书中给出了证明过程，下面的代码实现了上面的 getNearLessNoRepeat 方法。注意在下面的代码中没有重复数据的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[][] getNearLessNoRepeat(int[] arr) {
    int[][] res = new int[arr.length][0];
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = i;
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int popIndex = stack.pop();
        int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
        res[popLessIndex][0] = leftLessIndex;
        res[popLessIndex][1] = -1;
    }
    return res;
}

下面是我自己写的代码，真实没有对比就没有伤害，stack类没有add方法，将元素压入栈要用到push()方法。以后写代码遇到类似代码用三元运算符? :不要用if-else.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int[][] getNearLessNoRepeat(int[] arr) {
    int[][] res = new int[arr.length][2];
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < arr.length; i++) {
        if (stack.isEmpty || arr[stack.peek()]< arr[i]) {
            satck.add(i)
        } else {

            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                int cur = stack.pop();
                if (stack.isEmpty()) {
                    res[cur][0] = -1;
                } else {
                    res[cur][0] = stack.peek();
                }
                res[cur][1] = i;
            }
        }
    }
    while (!stack.isEmpty()) {
        int cur = stack.pop();
        if (stack.isEmpty()) {
            res[cur][0] = -1;
        } else {
            res[cur][0] = stack.peek();
        }
        res[cur][i] = -1;
    }
    return res;
}

进阶问题，可能含有重复值的数组如何使用单调栈。其实整个过程和原问题的解法差不多。举个例子来说明，初始时 arr={3,1,3,4,3,5,3,2,2}， stack 从栈顶到栈底为： {}；

遍历到 arr[0]=3，发现 stack 为空，就直接放入 0 位置。 stack 从栈顶到栈底为： {0 位置(值是 3)}；

遍历到 arr[1]=1，从栈中弹出位置 0，并且得到 ans[0]={-1,1}。位置 1 进栈， stack 从栈顶到栈底为： {1 位置(值是 1)}；

遍历到 arr[2]=3，发现位置 2 可以直接放入。 stack 从栈顶到栈底依次为： {2 位置(值是 3)、1 位置(值是 1)}；

遍历到 arr[3]=4，发现位置 3 可以直接放入。 stack 从栈顶到栈底依次为： {3 位置(值是 4)、2 位置(值是 3)、 1 位置(值是 1)}；

遍历到 arr[4]==3，从栈中弹出位置 3，并且得到 ans[3]={2,4}。此时发现栈顶是位置 2，值是 3，当前遍历到位置 4，值也是 3，所以两个位置压在一起。 stack 从栈顶到栈底依次为： { [2位置, 4 位置](值是 3)、 1 位置(值是 1)}；

遍历到 arr[5]=5，发现位置 5 可以直接放入。 stack 从栈顶到栈底依次为： { 5 位置(值是 5)、[2 位置, 4 位置](值是 3)、 1 位置(值是 1)}；

遍历到 arr[6]=3，从栈中弹出位置 5，在栈中位置 5 的下面是[2 位置, 4 位置]，选最晚加入的 4 位置，当前遍历到位置 6，所以得到 ans[5]={4,6}。位置 6 进栈，发现又是和栈顶位置代表的值相等的情况，所以继续压在一起， stack 从栈顶到栈底依次为： { [2 位置, 4 位置, 6 位置](值
是 3)、 1 位置(值是 1)}；

遍历到 arr[7]=2，从栈中弹出[2 位置, 4 位置, 6 位置]，在栈中这些位置下面的是 1 位置，当前是 7 位置，所以得到 ans[2]={1,7}、 ans[4]={1,7}、 ans[6]={1,7}。位置 7 进栈， stack 从栈顶到栈底依次为： {7 位置(值是 2)、 1 位置(值是 1)}；

遍历到 arr[8]==2，发现位置 8 可以直接进栈，并且又是相等的情况， stack 从栈顶到栈底依次为： {[7 位置, 8 位置](值是 2)、 1 位置(值是 1)}。

遍历完成后，开始清算阶段：

弹出[7 位置, 8 位置]，生成 ans[7]={1,-1}、 ans[8]={1,-1}；
弹出 1 位置，生成 ans[1]={-1,-1}。

总结上面的过程，也就是说，栈中存放的元素不再是一个Integer类型的值，而是一个List类型的值。

全部过程请看如下代码中的 getNearLess 方法。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int[][] getNearLess(int[] arr) {
    int[][] res = new int[arr.length][2];
    Stack<List<Integer>> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
        if (!stack.isEmpty() && arr[i] < arr[stack.peek.get(0)]) {
            List<Integer> popIs = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stak.peek().size() - 1);
            for (Integer popi : popIs) {
                res[popi][0] = leftLessIndex;
                res[popi][1] = i;
            }
        }
        if (!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]) {
            stack.peek().add(Integer.valueOf(i));
        } else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            stack.push(list);
        }
    }
    while (!stack.isEmpty()) {
        List<Integer> list = stack.pop();
        int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size - 1);
        for (Integer popi : popIs) {
            res[popi][0] = leftLessIndex;
            res[popi][1] = -1;
        }
    }
    return res;
}

【总结】

凡是求最近最小或者最近最大的问题，都用单调栈，这个思想很重要。

另外，stack没有add方法，有的是push方法。

List<Integer> 是接口实现类，因此不能直接创建对象；ArrayList 是 List 的具体实现类。

List<Integer> list = new ArrayList<>(); 是一种常见的写法。

题目九：求最大子矩阵的大小

【题目】

给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最大的矩形区域为 1 的数量。
例如：
1 1 1 0
其中， 最大的矩形区域有 3 个 1，所以返回 3。
再如：
1 0 1 1
1 1 1 1
1 1 1 0
其中， 最大的矩形区域有 6 个 1，所以返回 6。

【难度】

【解答】

如果矩阵的大小为 O(N×M)， 可以做到时间复杂度为 O(N×M)。解法的具体过程如下。

  1. 矩阵的行数为 N，以每一行做切割，统计以当前行作为底的情况下，每个位置往上的 1 的数量。使用高度数组 height 来表示。例如：

    1
    2
    3
    max = 1 0 1 1
          1 1 1 1
          1 1 1 0

    以第 1 行做切割后， height={1,0,1,1}， height[j]表示在目前的底（第 1 行） 的 j 位置往上（包括 j 位置）， 有多少个连续的 1。

    以第 2 行做切割后， height={2,1,2,2}， height[j]表示在目前的底（第 2 行） 的 j 位置往上（包括 j 位置）， 有多少个连续的 1。 注意到从第一行到第二行， height 数组的更新是十分方便的，即 height[j] = map[i][j]==0 ? 0 : height[j]+1。

    以第 3 行做切割后， height={3,2,3,0}， height[j]表示在目前的底（第 3 行） 的 j 位置往上（包括 j 位置）， 有多少个连续的 1。

  2. 对于每一次切割，都利用更新后的 height 数组来求出以当前行为底的情况下，最大的矩形是什么。那么这么多次切割中，最大的那个矩形就是我们要的答案。

整个过程就是题解代码中的 maxRecsize 方法， 步骤2的实现是题解代码中的maxRecFromBottom方法。

下面重点介绍一下步骤 2 如何快速地实现，这也是这道题最重要的部分，如果 height 数组的长度为 M，那么求解步骤 2 的过程可以做到时间复杂度为 O(M)。对于 height 数组，读者可以理解为一个直方图，比如{3,2,3,0}，其实就是下图所示的直方图。

也就是说，步骤 2 的实质是在一个大的直方图中求最大矩形的面积。如果我们能够求出以每一根柱子扩展出去的最大矩形，那么其中最大的矩形就是我们想找的。比如：

  • 第 1 根高度为 3 的柱子向左无法扩展， 它的右边是 2，比 3 小， 所以向右也无法扩展，则以第 1 根柱子为高度的矩形面积就是 3*1=3；

  • 第 2 根高度为 2 的柱子向左可以扩 1 个距离，因为它的左边是 3，比 2 大；右边的柱
    子也是 3， 所以向右也可以扩 1 个距离，则以第 2 根柱子为高度的矩形面积就是2*3=6；

  • 第 3 根高度为 3 的柱子向左没法扩展， 向右也没法扩展，则以第 3 根柱子为高度的矩
    形面积就是 3*1=3；

  • 第 4 根高度为 0 的柱子向左没法扩展， 向右也没法扩展，则以第 4 根柱子为高度的矩形面积就是 0*1=0；所以， 当前直方图中最大的矩形面积就是 6，也就是上图中虚线框住的部分。

考查每一根柱子最大能扩多大，这个行为的实质就是找到柱子左边离它最近且比它小的柱子位置在哪里，以及右边离它最近且比它小的柱子位置在哪里。这个过程怎么计算最快呢？ 利用单调栈，上一题单调栈结构中的算法正好可以用到这个问题上。

为了方便表述，我们以 height={3,4,5,4,3,6}为例说明如何根据 height 数组求其中的最大矩形。一共9个步骤，具体过程如下：

  1. 生成一个栈， 记为 stack，从左到右遍历 height 数组，每遍历一个位置， 都会把位置压进 stack 中。

  2. 遍历到 height 的 0 位置， height[0]=3，此时 stack 为空，直接将位置 0 压入栈中， 此时 stack 从栈顶到栈底为{0}。

  3. 遍历到 height 的 1 位置， height[1]=4，此时 stack 的栈顶为位置 0，值为 height[0]=3，又有 height[1]>height[0]，那么将位置 1 直接压入 stack。这一步体现了遍历过程中的一个关键逻辑：只有当前 i 位置的值 height[i]大于当前栈顶位置所代表的值（height[stack.peek()]）， 则 i位置才可以压入 stack。
    所以可以知道， stack 中从栈顶到栈底的位置所代表的值是依次递减， 并且无重复值，此时stack 从栈顶到栈底为{1,0}。

  4. 遍历到 height 的 2 位置， height[2]=5，与步骤 3 的情况完全一样，所以直接将位置 2 压
    入 stack，此时 stack 从栈顶到栈底为{2,1,0}。

  5. 遍历到 height 的 3 位置， height[3]=4，此时 stack 的栈顶为位置 2，值为 height[2]=5，又有height[3]<height[2]。此时又出现了一个遍历过程中的关键逻辑，即如果当前i位置的值height[i]小于或等于当前栈顶位置所代表的值（height[stack.peek()]），则把栈中存的位置不断弹出， 直到某一个栈顶所代表的值小于 height[i]，再把位置 i 压入，并在这期间做如下处理：

    5.1) 假设当前弹出的栈顶位置记为位置 j，弹出栈顶之后，新的栈顶记为 k。然后开始考虑位置 j 的柱子向右和向左最远能扩到哪里。
    5.2) 对位置 j 的柱子来说， 向右最远能扩到哪里呢？

    如果 height[j]>height[i]， 那么 i-1 位置就是向右能扩到的最远位置。 j 之所以被弹出， 就是因为遇到了第一个比 j 位置值小的位置。

    如果 height[j]==height[i]， 那么 i-1 位置不一定是向右能扩到的最远位置， 只是起码能扩到的位置。那怎么办呢？

    可以肯定的是， 在这种情况下， i 位置的柱子向左必然也可以扩到 j 位置。 也就是说， j 位置的柱子扩出来的最大矩形和 i 位置的柱子扩出来的最大矩形是同一个。

    所以， 此时 j 位置的柱子能扩出来的最大矩形虽然无法被正确计算， 但不要紧， 因为 i 位置肯定要压入到栈中， 那么 j 位置和 i 位置共享的最大矩形就等 i 位置弹出的时候再计算即可。

    5.3) 对位置 j 的柱子来说， 向左最远能扩到哪里呢？根据单调栈的性质， k 位置的值是 j 位置的值左边离 j 位置最近的比 j 位置的值小的位置，所以 j 位置的柱子向左最远可以扩到 k+1 位置。

    5.4) 综上所述， j 位置的柱子能扩出来的最大矩形为(i-k-1)*height[j]。以例子来说明。

    ① i=3， height[3]=4， 此时 stack 的栈顶为位置 2， 值为 height[2]=5， 故 height[3]<= height[2]，所以位置 2 被弹出（j=2）， 当前栈顶变为 1（k=1）。位置 2 的柱子扩出来的最大矩形面积为(3-1-1)*5=5。

    ② i=3， height[3]=4， 此时 stack 的栈顶为位置 1， 值为 height[1]=4， 故 height[3]<=height[1]，所以位置 1 被弹出（j=1）， 当前栈顶变为 1（k=0）。位置 1 的柱子扩出来的最大矩形面积为(3-0-1)*4=8， 这个值实际上是不对的（偏小）， 但在位置 3 被弹出的时候是能够重新正确计算
    得到的。

    ③ i=3， height[3]=4， 此时 stack 的栈顶为位置 0， 值为 height[0]=3， 这时 height[3]<=height[2]，所以位置 0 不弹出。

    ④ 将位置 3 压入 stack， stack 从栈顶到栈底为{3,0}。

  6. 遍历到 height 的 4 位置， height[4]=3。与步骤 5 的情况类似，以下是弹出过程：
    6.1) i=4， height[4]=3， 此时 stack 的栈顶为位置 3， 值为 height[3]=4， 故 height[4]<=height[3]，所以位置 3 被弹出（j=3）， 当前栈顶变为 0（k=0）。位置 3 的柱子扩出来的最大矩形面积为(4-0-1)*4=12。这个最大面积也是位置 1 的柱子扩出来的最大矩形面积， 在位置 1 被弹时，这个矩形其实没有找到， 但在位置 3 这里找到了。
    6.2) i=4， height[4]=3， 此时 stack 的栈顶为位置 0， 值为 height[0]=3， 故 height[4]<=height[0]，所以位置 0 被弹出（j=0）， 当前没有了栈顶元素，此时可以认为 k=-1。位置 0 的柱子扩出来的最大矩形面积为(4-(-1)-1)*3==12，这个值实际上是不对的（偏小），但在位置 4 被弹出时是能够重新正确计算得到的。
    6.3) 栈已经为空，所以将位置 4 压入 stack，此时从栈顶到栈底为{4}。

  7. 遍历到 height 的 5 位置， height[5]=6，情况和步骤 3 类似，直接压入位置 5，此时从栈
    顶到栈底为{5,4}。

  8. 遍历结束后， stack 中仍有位置没有经历扩的过程，从栈顶到栈底为{5,4}。此时因为 height数组再往右不能扩出去， 所以认为 i=height.length=6 且越界之后的值极小， 然后开始弹出留在栈中的位置：

    8.1) i=6， height[6]极小，此时 stack 的栈顶为位置 5，值为 height[5]=6， 故 height[6]<=height[5]，所以位置 5 被弹出（j=5），当前栈顶变为 4（k=4）。位置 5 的柱子扩出来的最大矩形面积为(6-4-1)*6=6。

    8.2) i=6， height[6]极小，此时 stack 的栈顶为位置 4，值为 height[4]=3， 故 height[6]<=height[4]，所以位置 4 被弹出（j=4），栈空了，此时可以认为 k=-1。位置 4 的柱子扩出来的最大矩形面积为(6-(-1)-1)*3=18。这个最大面积也是位置 0 的柱子扩出来的最大矩形面积，在位置 0 被弹出的时候， 这个矩形其实没有找到，但在位置 4 这里找到了。
    8.3) 栈已经空了，过程结束。

  9. 整个过程结束，所有找到的最大矩形面积中 18 是最大的，所以返回 18。

研究以上9个步骤时我们发现， 任何一个位置都仅仅进出栈1次， 所以时间复杂度为O(M)。既然每做一次切割处理的时间复杂度为O(M)，一共做N次， 那么总的时间复杂度为O(N×M)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int maxRecSize(int[][] map) {
    if(map == null || map.length == 0 || map[0].length = 0) {
        return 0;
    }
    int maxArea = 0;
    int[] height = new int[map[0].length];
    for (int i = 0 ; i < map.length; i++){
        for (int j = 0; j < height.length; j++) {
            height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
        }
        maxArea = Math.max(maxRecFromBottom(height), maxArea);
    }
    return maxArea;
}
public int maxRecFromBottom(int[] height) {
    if (height == null || height.length ==0) {
        return 0;
    }
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    for(int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] <= stack.peek()) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (i - k - 1) * height[j];
            maxArea = Math.max(curArea, maxArea);
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int j = stack.pop();
        int k = stack.isEmpty() ? -1 : stack.peek();
        int curArea = (height.length - k - 1);
        maxArea = Math.max(curArea, maxArea);
    }
    return maxArea;
}

题目十：最大值减去最小值小于或等于num的子数组数量

【题目】

给定数组 arr 和整数 num，共返回有多少个子数组满足如下情况：

max(arr[i..j]) - min(arr[i..j]) <= num

max(arr[i..j])表示子数组 arr[i..j]中的最大值， min(arr[i..j])表示子数组 arr[i..j]中的最小值。

【要求】

如果数组长度为N，请实现复杂度为O(N)的解法。

【难度】

【分析】

这道题可以解释为求出数组arr的所有子数组的最大值和最小值，然后比较最大值和最小值的差值与num的大小即可。

但是如果先求出所有的子数组，然后再分别求每个子数组的最大值和最小值，则非常耗时

【解答】

首先介绍普通的解法，找到 arr 的所有子数组，一共有 O(N2)个，然后对每一个子数组做遍历找到其中的最小值和最大值，这个过程的时间复杂度为 O(N)，然后看看这个子数组是否满足条件。统计所有满足的子数组数量即可。普通解法容易实现，但是时间复杂度为 O(N3)，本书不再详述。最优解可以做到时间复杂度为 O(N)，额外空间复杂度为 O(N)，在阅读下面的分析过程之前，请读者先阅读本章“生成窗口最大值数组”问题，本题所使用到的双端队列结构与解决“生成窗口最大值数组”问题中的双端队列结构含义基本一致。

生成两个双端队列 qmax 和 qmin。当子数组为 arr[i..j]时， qmax 维护了窗口子数组 arr[i..j]的最大值更新的结构， qmin 维护了窗口子数组arr[i..j]的最小值更新的结构。当子数组 arr[i..j]向右扩一个位置变成 arr[i..j+1]时， qmax 和 qmin 结构更新代价的平均时间复杂度为 O(1)，并且可以在 O(1)的时间内得到 arr[i..j+1]的最大值和最小值。当子数组 arr[i..j]向左缩一个位置变成arr[i+1..j]时， qmax 和 qmin 结构更新代价的平均时间复杂度为 O(1)，并且在 O(1)的时间内得到arr[i+1..j]的最大值和最小值。

通过分析题目满足的条件，可以得到如下两个结论：

  • 如果子数组 arr[i..j]满足条件，即 max(arr[i..j])-min(arr[i..j])<=num，那么 arr[i..j]中的每一个子数组，即 arr[k..l] （ i≤ k≤ l≤ j）都满足条件。我们以子数组 arr[i..j-1]为例说明， arr[i..j-1]最大值只可能小于或等于 arr[i..j]的最大值， arr[i..j-1]最小值只可能大于或等于 arr[i..j]的最小值，所以 arr[i..j-1]必然满足条件。同理， arr[i..j]中的每一个子数组都满足条件。
  • 如果子数组 arr[i..j]不满足条件，那么所有包含 arr[i..j]的子数组， 即 arr[k..l]（ k≤i≤j≤ l）都不满足条件。证明过程同第一个结论。

根据双端队列 qmax 和 qmin 的结构性质，以及如上两个结论，设计整个过程如下：

  1. 生成两个双端队列 qmax 和 qmin，含义如上文所说。生成两个整型变量 i 和 j，表示子数组的范围，即 arr[i..j]。生成整型变量 res，表示所有满足条件的子数组数量。
  2. 令 j 不断向右移动（ j++），表示 arr[i..j]一直向右扩大，并不断更新 qmax 和 qmin 结构，保证 qmax 和 qmin 始终维持动态窗口最大值和最小值的更新结构。一旦出现 arr[i..j]不满足条件的情况， j 向右扩的过程停止，此时 arr[i..j-1]、 arr[i..j-2]、 arr[i..j-3]…arr[i..i]一定都是满足条件的。
    也就是说，所有必须以 arr[i]作为第一个元素的子数组，满足条件的数量为 j-i 个。于是令 res+=j-i。
  3. 当进行完步骤 2，令 i 向右移动一个位置，并对 qmax 和 qmin 做出相应的更新， qmax和 qmin 从原来的 arr[i..j]窗口变成 arr[i+1..j]窗口的最大值和最小值的更新结构。然后重复步骤 2，也就是求所有必须以 arr[i+1]作为第一个元素的子数组中，满足条件的数量有多少个。
  4. 根据步骤 2 和步骤 3，依次求出：必须以 arr[0]开头的子数组，满足条件的数量有多少个；必须以 arr[1]开头的子数组，满足条件的数量有多少个；必须以arr[2]开头的子数组， 满足条件的数量有多少个， 全部累加起来就是答案。

上述过程中，所有的下标值最多进 qmax 和 qmin 一次，出 qmax 和 qmin 一次。 i 和 j 的值也不断增加，并且从来不减小。所以整个过程的时间复杂度为O(N)。

最优解全部实现请参看如下代码中的 getNum 方法。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int getNum(int[] arr, int num) {
    if (arr == null || arr.length == 0 || num == 0) {
        return 0;
    }
    LinkedList<Integer> qmax = new LinkedList<>();
    LinkedList<Integer> qmin = new LinkedList<>();
    int i = 0;
    int j = 0;
    int res = 0;
    while (i < arr.length) {
        while (j < arr.length) {
            if (qmin.isEmpty() || qmin.peekLast() != j) {
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                    qmin.pollLast();
                }
                qmin.addLast(j);
                while (!qmax.isEmpty() && arr[qmax.peeklast()] <= arr[j]) {
                    qmax.pollLast();
                }
                qmax.addLast(j);
            }
            if (qmax.peekFirst() - qmin.peekFirst() > num) {
                break;
            }
            j++;
        }
        res += j - i;
        if (qmin.peekFirst() == i) {
            qmin.pollFirst();
        }
        if (qmax.peekFirst() == i) {
            qmax.pollFirst();
        }
        i++;
    }
    return res;
}

【疑惑】

上面的代码中为何要做这样一个判断if (qmin.isEmpty() || qmin.peekLast() != j)?

题目十一：可见山峰对数量

【题目】

一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}、 {4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。 3->1->2->4->5->3 方向叫作 next 方向（逆时针）， 3->5->4->2->1->3 方向叫作 last 方向（顺时针）， 如下图所示：

山峰 A 和山峰 B 能够相互看见的条件为：
1． 如果 A 和 B 是同一座山，认为不能相互看见。

2． 如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。比如图 1-8 中，相邻的山峰对有(1,2)(2,4)(4,5)(3,5)(1,3)。

3． 如果 A 和 B 是不同的山， 并且在环中不相邻，假设两座山高度的最小值为 min。如果 A通过 next 方向到 B 的途中没有高度比 min 大的山峰，或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。比如图 1-8 中，高度为 3 的山和高度为 4 的山，两座山的高度最小值为 3。 3 从 last 方向走向 4，中途会遇见 5，所以 last 方向走不通； 3 从 next方向走向 4，中途会遇见 1 和 2，但是都不大于两座山高度的最小值 3，所以 next 方向可以走通。

有一个能走通就认为可以相互看见。再如， 高度为 2 的山和高度为 5 的山，两个方向上都走不通，所以不能相互看见。 图 1-8 中所有在环中不相邻，并且能看见的山峰对有(2,3)(3,4)。给定一个不含有负数且没有重复值的数组 arr，请返回有多少对山峰能够相互看见。

进阶问题： 给定一个不含有负数但可能含有重复值的数组 arr，返回有多少对山峰能够相互看见。

【要求】

如果 arr 长度为 N，没有重复值的情况下时间复杂度达到 O(1)，可能有重复值的情况下时间复杂度请达到 O(N)。

【难度】

原问题

进阶问题

【解答】

原问题： 时间复杂度 O(1)的解。如果数组中所有的数字都不一样，可见山峰对的数量可以由简单公式得到。环形结构中只有 1 座山峰时，可见山峰对的数量为 0；环形结构中只有 2 座山峰时，可见山峰对的数量为 1。这都是显而易见的。环形结构中有 i 座山峰时（i>2），可见山峰对的数量为 2×i-3。下面给出证明。
我们只用高度小的山峰去找高度大的山峰，而永远不用高度大的山峰去找高度小的山峰。比如题目描述中的例子，从 2 出发按照“小找大”原则，会找到(2,3)和(2,4)，但是不去尝试 2能不能看到 1，因为这是“大找小”， 而不是“小找大”。 (1,2)这一对可见山峰不会错过，因为从 1 出发按照“小找大”原则找的时候会找到这一对。从每一个位置出发，都按照“小找大”原则找到山峰对的数量，就是总的可见山峰对数量。如果有 i 座山峰并且高度都不一样，必然在环中存在唯一的最大值和唯一的次大值（第二大的值），如下图所示：

图中， x 节点表示除最高值和次高值之外的任何一座山峰，因为 x 既不是最大值， 也不是次大值，所以 x 在 last 方向上必存在第一个高度比它大的节点，假设这个节点是 y， y 有可能就是最大值节点，但是一定存在。 x 在 next 方向上必存在第一个高度比它大的节点，假设这个节点是 z， z 有可能就是次大值节点，但是一定存在。因为 y 是 x 在 last 方向上第一个高度比它大的节点，所以 x 在 last 方向上没到达 y 之前遇到的所有山峰高度都小于 x，不符合“小找大”方式。 同理， x 在 next 方向上没到达 z 之前遇到的所有山峰高度都小于 x，不符合“小找大”方式。同时根据可见山峰对的定义， y 从 last 方向到达 z 这一段的每一个节点 x 都看不见。所以从x 出发能找到且只能找到(x,y)和(x,z)这 2 对。如果环中有 i 个节点，除了最大值和次大值之外，还剩 i-2 个节点，这 i-2 个节点都根据“小找大”的方式，每一个都能找到 2 对，所以一共有(i-2)×2对，还有 1 对，就是次大值能够看见最大值这对。所以一共是 2×i-3 对。

进阶问题： 时间复杂度 O(N)的解。读者在阅读该解法之前，请先阅读并理解本书“单调栈结构”问题的解法。还是按照“小找大”的方式来求解可见山峰对个数，下面举例说明，假设环形山如图下图所示。

首先遍历一次环形山结构， 找到最大值的位置，如果最大值不止一个，找哪一个最大值都行。比如图 1-10 中 5 是最大值且不止一个，找到哪个都行，我们选择最下方的 5。准备一个栈，记为 stack， stack 中放入的是如下数据结构：

1
2
3
4
5
6
7
8
public class Record {
    public int value;
    public int times;
    public Record(int value) {
        this.value = value;
        this.times = 1;
    }
}

接下来从最大值开始沿着 next 方向准备再遍历一遍环形山。 stack 中先放入(5,1)，表示 5 这个高度，收集 1 个。以后放入记录时，都保证第一维的数字从顶到底是依次增大的。目前 stack从顶到底为： (5,1)。

沿 next 方向来到 4， 生成记录(4,1)，表示 4 这个数，收集 1 个。发现如果这个记录加入 stack，第一维的数字从顶到底是依次增大的，所以放入(4,1)。目前 stack 从顶到底依次为： (4,1)、 (5,1)。沿 next 方向来到 3， 生成记录(3,1)，表示 3 这个数，收集 1 个。发现如果这个记录加入 stack，第一维的数字从顶到底是依次增大的，所以放入(3,1)。目前 stack 从顶到底依次为： (3,1)、 (4,1)、(5,1)。

沿 next 方向来到 5， 生成记录(5,1)。发现如果这个记录加入 stack，第一维的数字从顶到底就不是依次增大的。所以 stack 开始弹出记录，首先弹出(3,1)，当前来到的数字是 5，当前弹出的数字是 3，原来在栈中的时候当前弹出数字的下面是 4， 说明当前弹出的 3 在 next 方向上遇到第一个大于它的数就是当前来到的数字 5，在 last 方向上遇到第一个大于它的数就是此时的栈顶 4。进一步说明从当前弹出的 3 出发，通过“小找大”的方式，可以找到 2 个可见山峰对，就是(3,4)和(3,5)。 stack 继续弹出记录(4,1)，当前来到的数字是 5，当前弹出的数字是 4，原来在栈中的时候，当前弹出数字下面的数字是 5， 说明从当前弹出的 4 出发，通过“小找大”的方式，又找到 2 个可见山峰对。 stack 从顶到底只剩下(5,1)这个记录，当前生成的新记录是(5,1)，把两个记录合并。目前 stack 从顶到底为： (5,2)，发现的山峰对数量为： 4。

沿 next 方向来到 4， 生成记录(4,1)。发现如果这个记录加入 stack，第一维的数字从顶到底是依次增大的，所以放入(4,1)。目前 stack 从顶到底依次为：(4,1)、 (5,2)，发现的山峰对数量：4。

沿 next 方向来到 2， 生成记录(2,1)。发现如果这个记录加入 stack，第一维的数字从顶到底是依次增大的，所以放入(2,1)。目前 stack 从顶到底依次为：(2,1)、 (4,1)、 (5,2)，发现的山峰对数量： 4。

沿 next 方向来到 4， 生成记录(4,1)。发现如果这个记录加入 stack，第一维的数字从顶到底就不是依次增大的了。所以 stack 开始弹出记录，首先弹出(2,1)，与上面的解释同理，可以发现2 个山峰对。此时 stack 顶部记录为(4,1)，把两个记录合并。目前 stack 从顶到底依次为： (4,2)、(5,2)，发现的山峰对数量： 6。

沿 next 方向来到 4， 生成记录(4,1)。此时 stack 顶部记录为(4,2)，把两个记录合并。目前 stack从顶到底依次为： (4,3)、 (5,2)，发现的山峰对数量： 6。

沿 next 方向来到 5。生成记录(5,1)， 发现如果这个记录加入 stack，第一维的数字从顶到底就不是依次增大的。所以 stack 弹出(4,3)，这条记录表示当前收集到的这 3 个 4 有可能相邻；或者即便是不相邻，中间夹的数字也一定小于 4（比如之前遇到的 2），并且所夹的数字一定已经用“小找大”的方式算过山峰对了（看看之前遇到的 2 在弹出的时候）， 如图下图所示。

图中虚线表示可能夹住某些数字，但都是比 4 小的，而且都是算过山峰对的数字，不需要去关心。那么这 3 个 4 一共产生多少对可见山峰呢？首先， 每一个 4 都可以看到 last 方向上的5 和 next 方向上的 5；其次， 这 3 个 4 内部，每两个 4 都可以相互看见。所以产生 2×3+C(2,3)=9对山峰。

总结一下。如果在遍历阶段，某个记录(X,K)从 stack 中弹出了，产生可见山峰对的数量为：

1）如果 K==1，产生 2 对。

2）如果 K>1，产生 2×K+C(2,K)对。

stack 在弹出(4,3)之后，当前顶部记录为(5,2)，当前生成的记录是(5,1)，合并在一起。目前stack 从顶到底为： (5,3)，发现的山峰对数量： 15。沿 next方向来到 3， 生成记录(3,1)。发现如果这个记录加入 stack，第一维的数字从顶到底是依次增大的，所以放入(3,1)。目前 stack 从顶到底依次为： (3,1)、(5,3)，发现的山峰对数量：15。

沿 next 方向来到 2， 生成记录(2,1)。发现如果这个记录加入 stack，第一维的数字从顶到底是依次增大的，所以放入(2,1)。目前 stack 从顶到底依次为：(2,1)、 (3,1)、 (5,3)，发现的山峰对数量： 15。

遍历完毕，在遍历过程中发现了 15 对山峰。进行最后一个阶段：单独清算栈中记录的阶段。这个阶段又分成 3 个小阶段。

第 1 个小阶段：弹出的记录不是栈中最后一个记录，也不是倒数第二个记录。

第 2 个小阶段：弹出的记录是栈中倒数第二个记录。

第 3 个小阶段：弹出的记录是栈中最后一个记录。

比如上面的例子，在最后单独清算栈中记录的阶段，就是 3 个小阶段都有，弹出(2,1)时是第 1 个小阶段， 弹出(3,1)时是第 2 个小阶段， 弹出(5,3)时是第 3个小阶段。 下图左是没有第 1小阶段，但是有 2、 3 小阶段的例子。

假设从最下方 5 开始，沿 next 方向遍历，遍历完成后， stack 从顶到底依次为： (4,2)、 (5,1)，然后进入清算阶段会发现没有第 1 小阶段。

假设从最下方 5 开始，沿 next 方向遍历，遍历完成后， stack 从顶到底为： (5,2)，然后进入清算阶段会发现没有第 1、 2 小阶段。如上图右所示。

任何环形结构都不可能出现没有第 3 小阶段的情况，因为我们总是从环形结构的最大值开始遍历的，它既然是整个环形结构的最大值，所以不会在遍历阶段的过程中被其他高度的山释放，一定会等到清算阶段时才会从栈中弹出。

在最后的清算阶段，假设从栈中弹出的记录为（X,K），那么产生山峰对的逻辑如下：

① 如果发现当前记录位于第 1 小阶段，产生山峰对为：如果 K==1，产生 2 对；如果 K>1，产生 2×K+C(2,K)对。这是因为（X,K） 这个记录弹出之后，剩下的记录大于或等于 2 条，而整个图形是环，说明这 K 个 X 在 last 方向和 next 方向一定都能找到大于它们高度的山。

举个例子，比如清算阶段时， stack 从顶到底依次为： (2,1)、 (3,1)、 (5,3)。在(2,1)弹出的时候，栈中还剩(3,1)、 (5,3)，说明这个 2 在 last 方向上能遇到 3，在 next 方向上会遇到 5（因为是环）。产生 2 对可见山峰。

再举个例子，比如清算阶段时， stack 从顶到底依次为： (1,7)、 (2,6)、 (3,10)、 (5,7)。在(1,7) 弹出的时候，栈中还剩(2,6)、 (3,10)、(5,7)。说明这 7 个 1 在 last 方向上能遇到 2，在 next 方向上会遇到 5（因为是环）。每个 1 都能看见 last 方向上的 2 和 next 方向上的 5，所以对外一共产生 7×2 个可见山峰对。 7 个 1 内部产生 C(2,7)个可见山峰对。

② 如果发现当前记录位于第 2 小阶段，也就是当前记录为栈中倒数第二条记录。那么需要查看栈中的最后一条记录，假设最后一条记录为（Y,M）。如果 M==1，产生1×K+C(2,K)对；如果M>1，产生 2×K+C(2,K)对。

③ 如果发现当前记录位于第 3 小阶段，也就是当前记录为栈中最后一条记录。这个 X 一定是环中的最大值。根据“小找大”的方式，对外不会产生山峰对，只是 K 个 X 内部产生山峰对。如果 K==1，产生 0 对；如果 K>1，产生 C(2,K)对。

根据单调栈的性质，全部过程的时间复杂度为 O(N)，请看如下的 getVisibleNum 方法。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public int getVisibleNum(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int size = arr.length;
    int maxIndex = 0;
    // 先在环中找到其中一个最大的位置，哪个都行
    for (int i = 0; i < size; i++) {
        maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
    }
    Stack<Record> stack = new Stack<Record>();
    // 先把（最大值，1）这个记录放到stack中
    stack.push(new Record(arr[maxIndex]));
    // 从最大值位置的下一个位置开始沿next方向遍历
    int index = nextIndex(maxIndex, size);
    // 用小找大的方式统计所有可见山峰对
    int res = 0;
    // 遍历阶段开始，当index再次回到maxIndex的时候，遍历结束
    while (index != maxIndex) {
        while (stack.peek().value < arr[index]) {
            int k = stack.pop.times;
            res += getInternalSum(k) + 2 * k;
        }
        if (stack.peek().value == arr[index]) {
            stack.peek().times++;
        } else {
            stack.push(new Record(arr[index]));
        }
        index = nextIndex(index, size);
    }

    // 清算第一小阶段
    while (stack.size() > 2) {
        int times = stack.pop().times;
        res += getInternalSum(times) + 2 * times;
    }

    // 清算第二小阶段
    if (stack.size() == 2) {
        int times = stack.pop().times;
        res += getInternalSum(times) + (stack.peek().times == 1 ? times : 2 * times);
    }

    // 清算第三小阶段
    res += getInternalSum (stack.pop().times);
    return res;
}

// 如果k==1，返回0；如果K>1，返回C(2,k)
public int getInternalNum(int k) {
    return k == 1 ? 0 : (k * (k - 1) / 2);
}

// 环形数组中当前位置为i，数组长度为size，返回i的下一个位置
public int nextIndex(int i, int size) {
    return i < (size - 1) ? (i + 1) : 0;
}