@[toc]

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

剑指offer

剑指 Offer 59 - II. 队列的最大值【中等】

题目链接：剑指 Offer 59 - II. 队列的最大值

题目内容：请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

思路：抓住关键点三个函数方法的时间复杂度都是O(1)，这个比较难顶。

1、双队列（符合题目要求）

复杂度分析：时间复杂度O(1)；空间复杂度O(n)

class MaxQueue {

    //定义两个队列，一个用来存储最大值，另一个用来存储所有入队的元素
    private Deque<Integer> res, max;

    public MaxQueue() {
        this.res = new LinkedList<>();
        this.max = new LinkedList<>();
    }
    
    public int max_value() {
        if (this.max.isEmpty()) {
            return -1;
        }
        return this.max.peekFirst();
    }
    
    public void push_back(int value) {
        this.res.offer(value);
        while (!this.max.isEmpty() && this.max.peekLast() < value) {
            this.max.removeLast();
        }
        this.max.offer(value);
    }
    
    public int pop_front() {
        if (this.res.isEmpty()) {
            return -1;
        }
        int res = this.res.poll();
        if (res == this.max.peekFirst()) {
            this.max.poll();
        }
        return res;
    }
}

2、遍历最大值。（不符合题意）

复杂度分析：时间复杂度O(n)，其中的max函数在每次调用时几乎都是O(n)，其他两个是O(1)；空间复杂度O(n)。

class MaxQueue {

    private int[] deque = new int[10000];
    private int begin, end;

    public MaxQueue() {
    }
    
    public int max_value() {
        int max = -1;
        for (int i = begin; i < end; i++) {
            max = Math.max(max, deque[i]);
        }
        return max;
    }
    
    public void push_back(int value) {
        deque[end++] = value;
    }
    
    public int pop_front() {
        if (end == begin) {
            return -1;
        }
        return deque[begin++];
    }
}

---

剑指 Offer 32 - I. 从上到下打印二叉树【中等】

题目链接：剑指 Offer 32 - I. 从上到下打印二叉树

题目内容：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

思路：

1、队列

复杂度分析：时间复杂度O(N)；空间复杂度O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        //队列
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) {
            deque.offer(root);
        }
        List<Integer> res = new ArrayList<>();
        while (!deque.isEmpty()) {
            TreeNode node = deque.poll();
            res.add(node.val);
            if (node.left != null) {
                deque.offer(node.left);
            }
            if (node.right != null) {
                deque.offer(node.right);
            }
        }
        //构造数组
        int[] resArr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resArr[i] = res.get(i);
        }
        return resArr;
    }
}

牛客网

用两个栈实现队列【简单】

题目链接：用两个栈实现队列

题目内容：用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

思路1：两个栈进行搭配操作。①入栈，直接入到第一个栈中。②出栈，将栈1中的全部推到栈2里，接着取出栈2中的第一个元素，之后将栈2里的元素再重新推到栈1中。

复杂度分析：

• 时间复杂度：push的时间复杂度为O(1),pop()为O(n)，遍历了两次栈。
• 空间复杂度：O(n)，借助了两个栈的空间。

import java.util.*;
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        //将所有栈1中的出栈到栈2
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        //此时从栈2中吐出来一个就是要出栈的元素
        int res = stack2.pop();
        //接着将栈2中的元素全部push到1中
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return res;
    }
}

---

leetcode

225. 用队列实现栈【简单】

学习：leetcode题解、 代码随想录— 225. 用队列实现栈

题目链接：225. 用队列实现栈

题目内容：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 Fals

提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

思路：

1、双队列实现

思路： 两个队列，出队通过队列1来进行。每插入一个元素，先插入到队列2，接着将队列1中的元素全部插入到队列2，接着队列1与队列2进行互换。之后重复操作。

①插入1
 队列1：[]  队列2：[1]
 队列1：[1]  队列2：[]
②插入2
 队列1：[1]  队列2：[2]
 队列1：[]  队列2：[1,2]
 队列1：[1,2]  队列2：[]
此时出队列顺序先是2，接着是1，此时就实现了栈。

代码：

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;//辅助队列，入队是先存储到该队列

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue2.offer(x);
        //将原本队列1中的内容进行存储到队列2（构成栈）
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        //交换queue1与queue2，因为之后使用的是queue1来进行出队
        Queue<Integer> tempQueue = queue1;
        queue1 = queue2;
        queue2 = tempQueue;
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

2、一个双端队列实现

思路：用一个双端队列来实现

每push一个数据就添加到队头，如下：
①添加1  [1]
②添加2  [1,2]
③添加3  [1,2,3]
之后pop出数据每次从队头获取
① pop() 取出3   [1,2]
② pop() 取出2   [1]
③ pop() 取出1   []
这样的添加与取方式就已经构成了栈的形式

代码：

class MyStack {

    //定义一个双端队列
    private Deque<Integer> queue;

    public MyStack() {
        queue = new ArrayDeque<>();
    }

    public void push(int x) {
        queue.offerFirst(x);//添加到队头
    }

    public int pop() {
        return queue.pollFirst();//出队头
    }

    public int top() {
        return queue.peekFirst();//打印队头数据
    }

    public boolean empty() {
        return queue.isEmpty();
    }
    
}

---

347. 前 K 个高频元素【中等】

学习：leetcode题解、 代码随想录—347.前 K 个高频元素

题目链接：347. 前 K 个高频元素

题目内容：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

思路：

1、哈希表+优先队列

思路：先使用哈希表来进行统计对应值的频率，之后创建一个优先队列设置一个从小到大排序的比较器，每次插入一组key、value后，判断当前的容量是否>k个，若是大于了直接将队头的出队(在队列里频率最小的)，最终遍历取出队列中的k组数据即可。

代码：

public int[] topKFrequent(int[] nums, int k) {
    //使用map来进行统计指定指定数的频率，key为num，value为频率
    Map<Integer,Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num,map.getOrDefault(num,0)+1);
    }
    Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
    //创建优先队列，传入Comparator匿名接口类，插入队列的元素从小到达排列
    PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue());
    for (Map.Entry<Integer, Integer> entry : entries) {
        queue.offer(entry);
        if(queue.size() > k){  //一旦队列中的数量大于k，直接将频率最小的出队(队头)
            queue.poll();
        }
    }
    //最终取出对应的最大k值
    int[] maxNums = new int[k];
    for (int i = k-1; i >=0 ; i--) {
        maxNums[i] = queue.poll().getKey();
    }
    return maxNums;
}

2、排序遍历+优先队列

思路：首先进行从小到大排序，之后对整个数组进行遍历，以[i]!=[i-1]来作为存储到队列的依据，队列按照从大到小排序，每次入队后判断是否>k个，若是大于出队。最终遍历k个即可获取到前k个高频元素。

代码：

public int[] topKFrequent(int[] nums, int k) {
    Arrays.sort(nums);
    //优先队列，按照频率从小到大排列(Comparator返回值为负数就从小到大排列，若是正数从大到小)
    PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> o1[1] - o2[1]);
    //对数组进行遍历操作
    int i = 1;
    int j = 1;
    for (; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            j++;
        } else {
            queue.offer(new int[]{nums[i - 1], j});
            if (queue.size() > k) {  //一旦大于原本k个数量就进行移除
                queue.poll();
            }
            j = 1;
        }
    }
    queue.offer(new int[]{nums[i - 1], j});
    if (queue.size() > k) {
        queue.poll();
    }
    //从队列中取出k个
    int[] maxNums = new int[k];
    for (int l = 0; l < k; l++) {
        maxNums[l] = queue.poll()[0];
    }
    return maxNums;
}

---

239. 滑动窗口最大值【困难】

学习：leetcode题解、 代码随想录— 239. 滑动窗口最大值

题目链接：239. 滑动窗口最大值

题目内容：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

示例 1：
输入：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

示例 2：
输入：nums = [1], k = 1
输出：[1]
 

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

思路：

1、自定义队列

思路： 自定义一种队列规则，将入队元素依次从队列后往前比对，若是有小于的直接出队直到碰到大于的时候停止，接着再入队，此时队列队头一直会是最大值。

示例：1,3,-1,-3,5,3,6,7  k=3
队列 deque=[],左边是队头 下面=>指的是拿到队头的元素值，并没有直接出队
① [1,3,-1],-3,5,3,6,7  首先先将第一组的元素入队，最终队列为[3]   => 3  
②  1,[3,-1,-3],5,3,6,7  将1出队(队头若是1就将1出队，实际无)，接着入队-3，-3与队列从后往前比，最终队列为[3,-3] => 3
③  1,3,[-1,-3,5],3,6,7  将3出队(队头若是3就将3出队。实际有)，接着入队5，5与队列往后往前比，最终队列为[5] => 5
④  1,3,-1,[-3,5,3],6,7  将-1出队(队头若是-1就将-1出队。实际无)，接着入队3，3与队列往后往前比，最终队列为[5，3] => 5
⑤  1,3,-1,-3,[5,3,6],7  将6出队(队头若是-3就将-3出队。实际无)，接着入队6，6与队列往后往前比，最终队列为[6] => 6
⑥  1,3,-1,-3,5,[3,6,7]  将5出队(队头若是5就将5出队。实际无)，接着入队7，7与队列往后往前比，最终队列为[7] => 7
最终每组值为[3,3,5,5,6,7]

代码：

class MyQueue{
    private Deque<Integer> deque;

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

    //添加元素时，将队列从后往前比num小的出列
    public void add(int num){
        while(!deque.isEmpty() && deque.getLast() < num){
            deque.pollLast();
        }
        deque.addLast(num);
    }

    //队头元素若是与num相同则出队
    public void pop(int num){
        if(!deque.isEmpty() && num == deque.getFirst()){
            deque.pollFirst();
        }
    }

    //获取队头元素(最大的值)
    public int peek(){
        return deque.getFirst();
    }

}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MyQueue myQueue = new MyQueue();
        int[] maxNums = new int[nums.length-k+1];
        //先将第一组的值放入，并且获取最大的值
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        maxNums[0] = myQueue.peek();
        for (int i = 1; i < maxNums.length; i++) {
            //进来先去除不在范围内的元素
            myQueue.pop(nums[i-1]);
            //添加新的元素
            myQueue.add(nums[i+k-1]);
            //获取出当前队列中最大的元素
            maxNums[i] = myQueue.peek();
        }
        return maxNums;
    }
}

2、窗口内比较值

思路：不使用某种数据结构，使用max、pos来临时存储最大值，max为最大值，pos为最大值索引。首先进行一轮比较得出对应的最大值，接着通过判断pos是否在下一次滑动窗口范围来进行相应的比较操作。

• 这里有一点不太清楚的是仅仅通过滑动窗口最左、最优右临界值来与最大值进行比较就能够让时间效率优化那么多？若是k为很大情况，那么临界最左-最右中间这些还是要一个一个进行比较，难道没有消耗特别多时间吗？(该题解与我最初思路一致，只不过没有想到的是多增加了下面第15行临界最左值判断就能优化时间效率那么多)

代码：

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] maxNums = new int[nums.length - k + 1];
    int pos = -1;
    int max = Integer.MIN_VALUE;
    for (int i = 0,winEndPos = k-1; i < maxNums.length; i++,winEndPos++) {
        if(pos >= i){
            if(nums[winEndPos] >= max){
                max = nums[winEndPos];
                pos = winEndPos;
            }
            //下面nums[winEndPos]、nums[i]相当于窗口的最右侧与最左侧
        }else if(nums[winEndPos] >= max-1){  //相当于>max，这里>=max-1，实际上是为了处理max = Integer.MIN_VALUE情况，-1由于超过原始长度就为最大值
            max = nums[winEndPos];
            pos = winEndPos;
        }else if(nums[i] >= max-1){
            max = nums[i];
            pos = i;
        }else{
            //若是上面两个情况不过，那么就需要进行遍历重新比出最大值
            max = nums[i];
            for (int j = i+1; j < i + k; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                    pos = j;
                }
            }
        }
        maxNums[i] = max;
    }
    return maxNums;
}