栈、队列与堆相关小结（剑指Offer相关题集合）

栈、队列与堆相关小结（剑指Offer相关题集合） 栈、队列与堆相关小结（剑指Offer相关题集合） 引言

最近在练习算法题时，发现有许多题都巧妙地运用了一些数据结构的特性，然后可以快速的求解问题，借此来做个小结。

首先在具体到每道题时，先介绍以下相关的结构：

栈: 栈具有先进后出的特点，它如同一个杯子，底部是封闭的，因此当一个数据先被压进栈，它会在栈底，而最后进栈的则会在栈顶，所以出栈的顺序则是最靠近栈顶的先出。

linkedList stack = new linkedList();

队列： 队列与栈不同，它并没有封闭的进出口，因此一个数据当从入口进队列时，也可以从出口出，具有先进先出的特点。要注意的是，在队列的结构中，有一种是双端队列，它可以由我们自己选择是从队列的头和尾进出队列。

// 单端队列
Queue queue = new ArrayList<>();
// 双端队列
Deque deque = new ArrayList<>();

堆： 堆的底层是一个二叉树结构，这也意味着它具有根结点，一般来说在做题时有时候会用到堆排序，但是更多的时候一般是用到优先队列，尽管叫做优先队列，但是实际上是一种堆结构，根结点是该队列中的最大值或最小值，成为大根堆和小根堆，小根堆在JAVA中是默认实现的，大根堆则需要我们自己修改比较器

// 小根堆
PriorityQueue smallHeap = new PriorityQueue();
// 大根堆
PriorityQueue bigHeap = new PriorityQueue((o1-o2) -> o2-o1)

剑指 Offer 40. 最小的k个数

题目描述：

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

示例：

Input: arr = [3,2,1], k = 2
Output: [1,2] 或者 [2,1]

Input: arr = [0,1,2,1], k = 1
Output: [0]

解题思路：

思路一：如果我们知道优先队列这一结构，那么我们可以将该数组的都放进小根堆中，再一一d出k个数，这k个数则是该数组中的最小值。

思路二：一般来说，我们很容易想到的是对该数组进行排序，排序比较快的算法有快速排序与归并排序，由于归并排序需要用到额外的空间，因此采用快速排序，但是实际上，快排的本质是通过一个数，将整体的左边与右边分离开，然后不断的进行左右递归，然后实现严格每个位置都有序。而本题要求的是，找到最小的k个数，也就是这k个数内部是怎么排序的并不关心，因此此时的划分条件就是，左边的k个数是小于右边的，从而可以对快排进行提前结束。

思路一算法代码：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k >= arr.length) return arr;  //当k比数组长度大时，直接返回。
        int[] res = new int[k];
        if (k == 0) { // 排除 0 的情况
            return res;
        }
        PriorityQueue queue = new PriorityQueue((o1,o2) -> o2-o1);
        for (int i = 0; i < k; ++i) {  // 将arr的前个数都放入到大根堆中
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {  // 从k+1个数开始，只放进比堆中最大值小的数，最后只剩下较小的数。
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {  // 此时堆中剩下的是最小的k个数。
            res[i] = queue.poll();
        }
        return res;
    }
}

思路二算法代码：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k>=arr.length) return arr;
        int[] res = quickSort(arr, 0, arr.length-1, k);
        return res;
        
    }
    public int[] quickSort(int[] nums, int left, int right, int k){
        int mid = partition(nums, left, right);
        if (k == mid) return Arrays.copyOfRange(nums, 0, k);
        return mid > k ? quickSort(nums, left, mid - 1, k): quickSort(nums, mid + 1, right, k);
    }
    public int partition(int[] nums, int left, int right){
        int temp = nums[left];
        while(left temp) right--;
            nums[left] = nums[right];
            while(left 
剑指 Offer 59 - I. 滑动窗口的最大值 
题目描述：
 
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
 
示例：
 
Input: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
 Output: [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
 
解题思路：
 
对于本题，我们一般最简单的思路是滑动窗口每进行一次滑动，都求出该滑动窗口的最大值，但是这会大大的增加时间复杂度，由于滑动一次算一次最大值，该遍历时间为O(n)， 而如果滑动窗口大小为O(k)，那么总的时间复杂度则为O(nk)，这是较高的。那么我们可以思考一下，既然我们每次都要移动滑动窗口的指针，那么就会有元素的增加和减少，我们是否可以在添加元素或者减少元素时，就得到新的滑动窗口的最大值呢？
 
大致思路是这样的，我们维护一个存储元素索引的队列，存储索引的好处是不仅可以获得数组值，还可以获得其位置。当滑动窗口的右指针向右移动时，那么就会有新元素加入，这时我们可以将其与原来滑动窗口的最大值作比较，如果比原来的最大值大，那么新进的元素则是该滑动窗口的最大值。那么原来滑动窗口的值该怎么办呢？自然是全部移除。**原因是，我们需要得到的是一个窗口的最大值，而刚进来的元素毫无以为是最后出去的，那么只要这个元素在，前面的元素永远不能成为最大值，自然留在队列中也没用了。**而当左指针向右移动时，我们要进行指针与当前最大值的索引进行比较，**如果指针超过了该索引，那么就应该将最大值去除，这时第二大的元素成为新的滑动窗口的最大值。**因此，总的来说，我们需要维护的是一个单调队列，并且该队列是双端的，队列的头永远是此刻滑动窗口的最大值。
 
偷个懒借个K神图
 
 
算法代码：
 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[k];
        int left = 0, right = 0;
        linkedList temp = new linkedList<>();
        int[] index = new int[nums.length - k + 1];
        while(right < nums.length){  // 初始移动右指针，形成滑动窗口。
            while(temp.size() != 0 && nums[right] >= nums[temp.peekLast()]){
                temp.pollLast();  // 当新进元素比旧元素大时，旧元素从队列尾移除
            }
            temp.addLast(right);  // 新进元素一定要进来，因为无法保证它不是第二大的，大不了在下一轮循环时，再把它去掉。
            if(right - left + 1 == k){
                break;
            }
            right ++;
        }
        while(right < nums.length){
            if(left > temp.peekFirst()) temp.pollFirst();  // 当左指针超过当前滑动窗口的最大值时，移除。
            while(temp.size() != 0 && nums[right] >= nums[temp.peekLast()]){
                temp.pollLast();
            }
            temp.addLast(right);
            index[left] = temp.peekFirst();  
            left ++;
            right ++;
        }
        int[] res = new int[index.length];
        for (int i = 0; i < res.length; i++){
            res[i] = nums[index[i]];
        }
        return res;
    }
}
 
剑指 Offer 59 - II. 队列的最大值 
题目描述：
 
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
 
若队列为空，pop_front 和 max_value 需要返回 -1
 
示例：
 
Input:["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]]
 Output:[null,null,null,2,1,2]
 
Input:["MaxQueue","pop_front","max_value"] [[],[],[]]
 Output:[null,null,null,2,1,2]
 
解题思路：
 
其实这题跟上一题滑动窗口的最大值十分类似，只是这次的滑动窗口替换成了一个队列的最大值，但是最大值仍然需要一个双端队列来维护。
 
算法代码：
 
class MaxQueue {
    Queue q;
    Deque d;
    public MaxQueue() {
        q = new linkedList<>();
        d = new linkedList<>();
    }
    
    public int max_value() {
        if(d.isEmpty()) return -1;
        return d.peekFirst();
    }
    
    public void push_back(int value) {
        q.offer(value);
        while(!d.isEmpty() && value > d.peekLast()){
            d.pollLast();
        }
        d.offerLast(value);
    }
    
    public int pop_front() {
        if(q.isEmpty()) return -1;
        int value = q.poll();
        if(value == d.peek()) d.pollFirst();
        return value;
    }
}
 
剑指 Offer 41. 数据流中的中位数 
题目描述：
 
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 
例如，[2,3,4] 的中位数是 3。[2,3] 的中位数是 (2 + 3) / 2 = 2.5
 
设计一个支持以下两种 *** 作的数据结构：void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。
 
示例：
 
Input:["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]
 Output:[null,null,null,1.50000,null,2.00000]
 
Input:["MedianFinder","addNum","findMedian","addNum","findMedian"] [[],[2],[],[3],[]]
 Output:[null,null,2.00000,null,2.50000]
 
解题思路：
 
这题在leetcode 中属于困难题，因为如果不知道使用相关的数据结构，这题就非常难做出，但是如果想到了优先队列这一结构，就会有思路。由于中位数是由中间的一个数或者两个数决定的，那么我们就可以试着将数据流中的数分为两个部分，一部分是比中间值小的那部分，一部分是比中间值大的那部分，最后我们取出其中一部分的最大值与一部分的最小值，这样我们就可以算出中位数（注意，我们是以偶数个数值举例子）。那么用什么维护，并且可以快速的取出最大值和最小值呢，自然是我们上面提到过的优先队列。
 
为了保证加入到大根堆小根堆的值一定是较小或较大的，我们可以先把新来的数加入到一个堆中，然后再从该堆中d出一个数，d出的数在加入另一个堆中，这样就可以保证两个堆分别维护的是较大值和较小值。
 
算法代码：
 
class MedianFinder {
    Queue A,B;
    
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x,y) -> (y-x));
    }
    
    public void addNum(int num) {
        if(A.size()!=B.size()){  // 这里我们选择的是当数据流为奇数时，让A中的数多出一个。这样中位数则是A的峰顶值。
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size()==B.size()? (A.peek() + B.peek()) / 2.0 :A.peek();
    }
}
 
后续如果做到相关题目会继续补充
 如有错误，大家指出，一起进步！
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5692902.html