code 原作者：画手大鹏
链接：https://leetcode-cn.com/leetbook/read/illustrate-lcof/59otf1/
来源：力扣（LeetCode）

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/ohvl0d/
来源：力扣（LeetCode）

code 原作者2：CyC2018
链接：https://github.com/CyC2018/CS-Notes
来源：GitHub

1. 栈（Stack）
   1. 剑指 Offer 06. 从尾到头打印链表
   2. 剑指 Offer 9. 用两个栈实现队列
   3. 剑指 Offer 30. 包含 min 函数的栈
   4. 剑指 Offer 31. 栈的压入、弹出序列
   5. 剑指 Offer 40. 最小的 K 个数
   6. 剑指 Offer 41.1 数据流中的中位数
   7. 剑指 Offer 59 - I. 滑动窗口的最大值
   8. 剑指 Offer 59 - II. 队列的最大值

栈（Stack）

剑指 Offer 06. 从尾到头打印链表

题目描述

• 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

**思路**

• 标签：栈 （用 LinkedList 来模拟）
• 栈的特点是先进后出，因为题目要求从尾到头打印元素，所以符合栈的特性
• 先遍历一遍链表，将链表中的元素存入到栈中
• 再不断弹出栈内元素，将弹出元素存放到结果数组中
• 也有使用递归来进行解题的，在此提出一个思考，递归和栈的关系是什么？其实递归的本质也是在使用栈，只不过是程序调用栈，因为没有显式在代码中体现出来，所以常常被忽略了
• 时间复杂度：O(n)，空间复杂度：O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode pointer = head; // copy the address of head 
        while (pointer != null) {
            stack.addLast(pointer);
            pointer = pointer.next;
        }

        int length = stack.size();
        int[] res = new int[length];
        for(int i = 0; i < length; i++) {
            res[i] = stack.removeLast().val; 
        }
        return res;
    }
}

剑指 Offer 9. 用两个栈实现队列

题目描述

• 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。（若队列中没有元素，deleteHead 操作返回 -1）

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

• 1 <= values <= 10000
• 最多会对 appendTail、deleteHead 进行 10000 次调用

解题思路

思路

• 标签：栈和队列 (用 LinkedList 来模拟)
• 整体思路：栈实现队列的本质就是负负得正，两次先进后出的结果就是先进先出了。在构造函数中完成两个栈的初始化工作，在 appendTail 函数中向其中一个栈 in 结尾插入整数，在 deleteHead 函数中如果 out 为空，则将 in 的值全部弹出放到 out 中，再从 out 中取值，这样达到了负负为正的队列效果
• in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。
• 时间复杂度：O(1)，空间复杂度：O(n)

算法流程

• CQueue 构造函数，初始化 in 和 out
• appendTail 函数，将 value 加到 in 里面，先进后出
• deleteHead 函数，判断 out 是否为空，如果为空则将当前 in 中的所有值都弹出放入 out 中。此时由于 out 也是先进后出，所以如果 out 不为空，则将其尾部值弹出，实现了先进先出队列的效果，如果 out 为空，则返回 -1

class CQueue {
    LinkedList<Integer> in;
    LinkedList<Integer> out;

    public CQueue() {
        in  = new LinkedList<Integer>();
        out = new LinkedList<Integer>();
    }

    public void appendTail(int value) {
        in.addLast(value);
    }

    public int deleteHead() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.addLast(in.removeLast());
            }
        }
        if (out.isEmpty())
            return -1;

    	return out.removeLast();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 */

剑指 Offer 30. 包含 min 函数的栈

题目描述

• 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

• 各函数的调用总次数不超过 20000 次

解题思路

使用一个额外的 minStack，栈顶元素为当前栈中最小的值。在对栈进行 push 入栈和 pop 出栈操作时，同样需要对 minStack 进行入栈出栈操作，从而使 minStack 栈顶元素一直为当前栈中最小的值。在进行 push 操作时，需要比较入栈元素和当前栈中最小值，将值较小的元素 push 到 minStack 中。

思路

• 标签：辅助栈 （用 LinkedList 来模拟）
• 整体思路：push、pop、top 操作可以通过建立普通的栈结构完成操作，对于取最小值 min 函数则需要建立辅助栈，辅助栈中降序存储 push 过程中的值
• 时间复杂度：O(1)，空间复杂度：O(n)

算法流程

• MinStack 构造函数中初始化数据栈 stack1 和辅助栈 stack2
• push 函数中将 x 正常添加到 stack1 中，如果 stack2 为空或者 stack2 栈顶值大于等于 x 时，则将 x 加入 stack2 中，这样保证了 stack2 中的值一定是降序的，存储的数量会小于等于 stack1
• pop 函数中首先 stack1 需要将值 pop 出去，如果 stack2 栈顶数据与 stack1 栈顶数据相等，则将 stack2 的值也 pop 出去，保证数据栈和辅助栈的数据一致性
• top 函数则直接取 stack1 栈顶值即可
• min 函数则直接取 stack2 栈顶值即可

class MinStack {
    private LinkedList<Integer> stack1;
    private LinkedList<Integer> stack2;
    
    public MinStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void push(int x) {
        stack1.addLast(x);
        if(stack2.isEmpty() || stack2.peekLast() >= x) {
            stack2.addLast(x);
        }

    }

    public void pop() {
        if(stack1.removeLast().equals(stack2.peekLast())) {
            stack2.removeLast();
        }
    }

    public int top() {
        return stack1.peekLast();
    }

    public int min() {
        return stack2.peekLast();
    }
}

剑指 Offer 31. 栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1:

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

限制：

• 0 <= pushed.length == popped.length <= 1000
• 0 <= pushed[i], popped[i] < 1000
• pushed 是 popped 的排列。

思路

• 标签：模拟 （用 LinkedList 来模拟）

• 整体思路：

• 借用一个辅助栈 stack，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。

• 复杂度：

  • 时间复杂度：O(n)。 nn 为入栈序列的长度

  • 空间复杂度：O(n)： 辅助栈最多存储 nn 个元素

算法流程

• 建立一个辅助栈
• 遍历入栈序列
  • 元素入栈
  • 若辅助栈栈顶元素等于弹出序列元素，则执行出栈操作
• 返回结果

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        int i = 0;
        for(int element : pushed) {
            stack.addLast(element); // num 入栈
            while(!stack.isEmpty() && stack.peekLast() == popped[i]) { // 循环判断与出栈
                stack.removeLast();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

剑指 Offer 40. 最小的 K 个数

题目描述

• 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

解题思路

• 大小为 K 的最小堆

• 复杂度：O(NlogK) + O(K)

• 特别适合处理海量数据

• 维护一个大小为 K 的最小堆过程如下：使用大顶堆。在添加一个元素之后，如果大顶堆的大小大于 K，那么将大顶堆的堆顶元素去除，也就是将当前堆中值最大的元素去除，从而使得留在堆中的元素都比被去除的元素来得小。

• 应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。

• Java 的 PriorityQueue 实现了堆的能力，PriorityQueue 默认是小顶堆，可以在在初始化时使用 Lambda 表达式 (o1, o2) -> o2 - o1 来实现大顶堆。其它语言也有类似的堆数据结构。

public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
    if (k > nums.length || k <= 0)
        return new ArrayList<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x, y) -> y - x);//Comparator.comparing(Integer -> Integer)
    for (int num : nums) {
        maxHeap.add(num);
        if (maxHeap.size() > k)
            maxHeap.poll();
    }
    return new ArrayList<>(maxHeap);
}


// return int array 
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k > arr.length || k <= 0)
        return new int [k];
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.comparing(Integer -> Integer));
    for (int num : arr) {
        maxHeap.add(num);
        if (maxHeap.size() > k)
            maxHeap.poll();
    }
    int [] min = new int[k];
    for (int i = 0; i < k; i++)
        min[i] = maxHeap.poll();
    return min;
    }
}

剑指 Offer 41.1 数据流中的中位数

题目描述

• 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

• 例如，

  • [2,3,4] 的中位数是 3
  • [2,3] 的中位数是 (2 + 3) / 2 = 2.5

• 设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

• 最多会对 addNum、findMedian 进行 50000 次调用。

解题思路

/* 大顶堆，存储左半边元素 */
private PriorityQueue<Integer> left = new PriorityQueue<>((x, y) -> y - x);
/* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */
private PriorityQueue<Integer> right = new PriorityQueue<>();
/* 当前数据流读入的元素个数 */
private int N = 0;

public void Insert(Integer val) {
    /* 插入要保证两个堆存于平衡状态 */
    if (N % 2 == 0) {
        /* N 为偶数的情况下插入到右半边。
         * 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
         * 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */
        left.add(val);
        right.add(left.poll());
    } else {
        right.add(val);
        left.add(right.poll());
    }
    N++;
}

public Double GetMedian() {
    if (N % 2 == 0)
        return (left.peek() + right.peek()) / 2.0;
    else
        return (double) right.peek();
}

解题思路

• 给定一长度为 N 的无序数组，其中位数的计算方法：首先对数组执行排序（使用 O(N log N) 时间），然后返回中间元素即可（使用 O(1) 时间）。

• 针对本题，根据以上思路，可以将数据流保存在一个列表中，并在添加元素时 保持数组有序 。此方法的时间复杂度为 O(N)，其中包括： 查找元素插入位置 O(log N) （二分查找）、向数组某位置插入元素 O(N)（插入位置之后的元素都需要向后移动一位）。

• 借助 堆 可进一步优化时间复杂度。

• 建立一个 小顶堆 A 和 大顶堆 B ，各保存列表的一半元素，且规定：

  • AA 保存 较大 的一半，长度为 （ N 为偶数）或 （ NN 为奇数）；
  • BB 保存 较小 的一半，长度为 （ NN 为偶数）或 （ NN 为奇数）；

• 随后，中位数可仅根据 A, B 的堆顶元素计算得到。

剑指 Offer 59 - I. 滑动窗口的最大值

题目描述

• 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值

---------------               -----

[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

• 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

思路

• 标签：单调队列
• 整体思路：
  • 从题目上来看是通过维护滑动窗口，然后每次求滑动窗口中的最大值即可，设数组长度为 n，窗口长度为 k，则时间复杂度为 O(k*(n-k+1)) = O(kn)
  • 很显然使用暴力解法的话，时间复杂度会随着 k 变大不断变大，而其中有很多元素在不同的滑动窗口中都存在着，所以必然存在重复计算的逻辑
  • 考虑使用单调队列，队列内只存在窗口内的元素，队列内元素递减。可以保证所有的数据只会入队和出队一次，减少时间复杂度
• 复杂度：
  • 时间复杂度：O(n)。遍历数组需要 O(n) 的时间复杂度，数组中的元素最多入队和出队一次，队列内元素维护最多需要 O(2n) ，所以总体时间复杂度为 O(n)
  • 空间复杂度：O(k)。维护一个最多元素个数为 k 个的队列

算法流程

• 初始化滑动窗口的 left 和 right 位置，从下标为 [1-k, 0] 范围开始
• 如果 left > 0 说明窗口已经在数组中了，并且单调队列的第一个元素和 nums[left - 1] 相等时，说明该元素已经不在滑动窗口中，需要移除
• 如果单调队列不为空且最后一个元素小于新加入的 nums[right] 元素，则需要维护单调队列为递减状态，所以将最后一个元素移除，直到其大于新加入元素
• 将新加入的 nums[right] 元素加入单调队列，因为上一步的操作，当前单调队列一定是递减的
• 如果 left >= 0，说明窗口在数组中，因为单调队列递减，所以第一个元素一定是当前滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) {
            return new int[0];
        }
        
        Deque<Integer> queue = new LinkedList<>();
        
        int[] res = new int[nums.length - k + 1];
        
        for(int right = 0, left = 1 - k; right < nums.length; left++, right++) {
            // 如果 left > 0 说明窗口已经在数组中了，并且单调队列的第一个元素和 nums[left - 1] 相等时，说明该元素已经不在滑动窗口中，需要移除
            if(left > 0 && queue.peekFirst() == nums[left - 1]) {
                queue.removeFirst();
            }
            
            // 如果单调队列不为空且最后一个元素小于新加入的 nums[right] 元素，则需要维护单调队列为递减状态，所以将最后一个元素移除, 直到其大于新加入元素
            while(!queue.isEmpty() && queue.peekLast() < nums[right]) {
                queue.removeLast();
            }
            
            // 将新加入的 nums[right] 元素加入单调队列，因为上一步的操作，当前单调队列一定是递减的
            queue.addLast(nums[right]);
            
            // 如果 left >= 0，说明窗口在数组中，因为单调队列递减，所以第一个元素一定是当前滑动窗口最大值
            if(left >= 0) {
                res[left] = queue.peekFirst();
            }
        }
        return res;
    }
}

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

题目描述

• 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数 max_value、push_back 和 pop_front 的均摊时间复杂度都是 O(1)。
• 若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

• 1 <= push_back,pop_front,max_value的总操作数 <= 10000
• 1 <= value <= 10^5

思路

• 标签：单调队列、辅助队列
• 整体思路：
  • 这道题和 59 - I 的思路很像，最难的地方在于取出最大值函数的时间复杂度如何降为 O(1)，如果每次入队的时候都维护一个最大值，那么时间复杂度很明显不满足条件
  • 使用一个额外的辅助单调队列，该队列单调递减即可，保证最大值在队列头部，这样的话就可以在取出最大值的时候时间复杂度减低
• 复杂度：
  • 时间复杂度：O(1)。取 max_value 时只需要取单调队列头部即可
  • 空间复杂度：O(n)。一共需要维护两个队列，普通队列和辅助单调队列，最差的情况是两个队列里面 n 个数字

算法流程

• 构造函数中初始化一个普通队列 queue 和一个辅助单调队列 deque
• max_value 函数中只需要每次从辅助单调队列 deque 取头部值即可，如果没有则返回 -1
• push_back 函数中首先将值放入 queue 中，然后将 deque 尾部所有小于该值的元素都剔除，最后将该值放入尾部，保证单调队列递减
• pop_front 函数中首先获取 queue 头部值 head，如果不存在则返回 -1，然后判断 deque 的头部值是否和 head 相等，如果相等则将其头部值也移除

class MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> deque;

    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }

    // max_value 函数中只需要每次从辅助单调队列 deque 取头部值即可，如果没有则返回 -1
    public int max_value() {
        return deque.size() > 0 ? deque.peek() : -1;
    }

    public void push_back(int value) {
        // 首先将值放入 queue 中
        queue.offer(value);
        
        // 将 deque 尾部所有小于该值的元素都剔除
        while(deque.size() > 0 && deque.peekLast() < value){
            deque.pollLast();
        }
        
        // 最后将该值放入尾部，保证单调队列递减
        deque.offerLast(value);
    }

    public int pop_front() {
        // 首先获取 queue 头部值 head
        int head = queue.size() > 0 ? queue.poll() : -1;
        
        // 判断 deque 的头部值是否和 head 相等，如果相等则将其头部值也移除
        if(deque.size() > 0 && deque.peek().equals(head)){
            deque.poll();
        }
        return head;
    }
}
/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */