剑指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; }
