重庆做网站及公众号公司,免费logo素材,wordpress 作者页面,互联网公司是什么文章目录 【LeetCode热题100】打卡第42天#xff1a;滑动窗口最大值搜索二维矩阵II⛅前言 滑动窗口最大值#x1f512;题目#x1f511;题解 搜索二维矩阵II#x1f512;题目#x1f511;题解 【LeetCode热题100】打卡第42天#xff1a;滑动窗口最大值搜索二维… 文章目录 【LeetCode热题100】打卡第42天滑动窗口最大值搜索二维矩阵II⛅前言 滑动窗口最大值题目题解 搜索二维矩阵II题目题解 【LeetCode热题100】打卡第42天滑动窗口最大值搜索二维矩阵II
⛅前言 大家好我是知识汲取者欢迎来到我的LeetCode热题100刷题专栏 精选 100 道力扣LeetCode上最热门的题目适合初识算法与数据结构的新手和想要在短时间内高效提升的人熟练掌握这 100 道题你就已经具备了在代码世界通行的基本能力。在此专栏中我们将会涵盖各种类型的算法题目包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等并会提供详细的解题思路以及Java代码实现。如果你也想刷题不断提升自己就请加入我们吧QQ群号827302436。我们共同监督打卡一起学习一起进步。 博客主页知识汲取者的博客 LeetCode热题100专栏LeetCode热题100 Gitee地址知识汲取者 (aghp) - Gitee.com 题目来源LeetCode 热题 100 - 学习计划 - 力扣LeetCode全球极客挚爱的技术成长平台 PS作者水平有限如有错误或描述不当的地方恳请及时告诉作者作者将不胜感激 滑动窗口最大值
题目 原题链接239.滑动窗口最大值 题解 解法一递减队列 所谓的递减队列就是队头到队尾的元素按照从大到小的顺序进行排序的 算法的核心步骤 添加元素要保障单调队列中的元素是递减的由于添加元素是在队尾进行的所以要求队列中其他元素都要比它大移除元素由于移除元素是在队头进行的如果当前元素是最大值需要移除单调队列的队头元素队头元素就是当前最大值 对于这种题目我现在也不是一开始就没有思路了一下就想到肯定要使用 递减队列 但是目前实现起来还是有一点困难经过不断的debug调试然后再不断优化代码的语句和逻辑判断最终还是实现了现在我就来说说我实现的思路吧我们①首先需要构建两个队列一个队列可以是普通队列用于存储滑动窗口中的元素一个队列只能是双端队列用于记录当前窗口最大值②这个双端队中的元素是递减的这样能够保障队尾元素总是当前最大元素我们要获取当前最大元素只需要获取队尾元素即可③移除元素时如果发现移除的元素是当前最大值需要移除双端队列的队尾元素这里不罗嗦了直接画图吧 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m8f6nOFf-1690024629049)(https://gitee.com/aghp/typora-img/raw/master/csdn/202307221916698.gif)] 本题可以参考【LeetCode热题100】打卡第35天最小栈 import java.util.Deque;
import java.util.LinkedList;/*** author ghp* title*/
public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] ans new int[nums.length - k 1];DescQueue queue new DescQueue();// 初始化窗口for (int i 0; i k; i) {queue.add(nums[i]);}int j 0;ans[j] queue.getMax();// 向右滑动窗口for (int i k; i nums.length; i) {queue.remove();queue.add(nums[i]);ans[j] queue.getMax();}return ans;}
}class DescQueue {private DequeInteger queue;private DequeInteger maxQueue;public DescQueue() {this.queue new LinkedList();this.maxQueue new LinkedList();}/*** 新增元素到队列尾部** param val*/public void add(int val) {queue.offer(val);while (!maxQueue.isEmpty() maxQueue.peekLast() val) {// 新增元素大于maxQueue队尾元素不符合递减队列的要求// 需要移除队尾元素直到maxQueue符合递减队列为止maxQueue.pollLast();}// 新增元素大于等于队尾元素符合递增队列直接添加到队尾maxQueue.offer(val);}/*** 移除队列头部元素*/public void remove() {int val queue.poll();if (val maxQueue.peek()) {// 移除的队头元素是当前最大值则需要更新maxQueuemaxQueue.poll();}}/*** 获取当前队列中最大元素** return*/public int getMax() {// maxQueue的头部元素即为当前最大值直接返回即可return maxQueue.peek();}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) 其中 n n n 为数组中元素的个数 这里需要了解一下队列的几个常用API不要搞混了队列是队尾进队头出队尾操作有offer、pollLast、peekLast、getLast队头操作有poll、peek、element、getFirst 代码优化空间优化 前面我们使用了两个队列一个队列存储窗口中的元素一个队列记录当前最大值我们可以发现对于本题我们其实可以发现我们只需要知道当前窗口中的最大值即可并不需要去记录当前窗口中所有的元素所以这里我们可以对上面的代码进行一个改造从而省略一个队列的开销从而一定程度降低空间复杂度那么我们该如何实现呢这里给出主要思路 添加元素要保障单调队列中的元素是递减的由于添加元素是在队尾进行的所以要求队列中其他元素都要比它大移除元素我们不必像之前一样直接移除左边界元素但是我们队列中存储的数组的索引我们可以换一种思路只有当最大值被移除时才更新递减队列DescQueue 总的思路还是和上一题大差不差的空间复杂度没有降低但是减少了内存占用 备注优化参考LeetCode官方题解 import java.util.Deque;
import java.util.LinkedList;/*** author ghp* title*/
public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] ans new int[nums.length - k 1];DescQueue queue new DescQueue();// 初始化窗口for (int i 0; i k; i) {queue.add(nums, i);}ans[0] nums[queue.getMax()];// 向右滑动窗口for (int i k; i nums.length; i) {queue.remove(i - k);queue.add(nums, i);ans[i - k 1] nums[queue.getMax()];}return ans;}
}class DescQueue {private DequeInteger maxQueue;public DescQueue() {this.maxQueue new LinkedList();}/*** 新增元素到队列尾部** param arr* param i*/public void add(int[] arr, int i) {while (!maxQueue.isEmpty() arr[i] arr[maxQueue.peekLast()]) {// 新增元素大于maxQueue队尾元素不符合递减队列的要求// 需要移除队尾元素直到maxQueue符合递减队列为止maxQueue.pollLast();}// 新增元素大于等于队尾元素符合递增队列直接添加到队尾maxQueue.offer(i);}/*** 移除队列头部元素*/public void remove(int i) {while (!maxQueue.isEmpty() maxQueue.peek() i) {// 队头元素的索引已经超出了左边界直接移除队头元素已过期maxQueue.poll();}}/*** 获取当前队列中最大元素** return*/public int getMax() {// maxQueue的头部元素即为当前最大值直接返回即可return maxQueue.peek();}
}解法二优先队列 优先队列可能比前面的单调队列还要简单很多思路也超级简单这里就简单讲解一下 构造优先队列这一步是核心步骤我们创建一个优先队列队列中的元素是一个数组数组的第一个元素是添加的nums数组的值第二个元素是nums数组值对应的索引添加元素直接添加即可优先队列底层会通过维护一个大根堆实现降序排序即队头元素到队尾元素的值从大到小排序 其实说白了优先队列本质也是一个单调队列思想只是这个单调对了不需要我们自己维护相较于解法一本方法就简单太多了 import java.util.PriorityQueue;/*** author ghp* title*/
public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] ans new int[nums.length - k 1];// 创建一个优先队列并且根据数组第一个元素进行降序排列第一个元素是值第二个元素是索引PriorityQueueint[] pq new PriorityQueue((a, b) - b[0] - a[0]);// 初始化窗口for (int i 0; i k; i) {pq.offer(new int[]{nums[i], i});}int j 0;ans[j] pq.peek()[0];// 向右滑动窗口for (int i k; i nums.length; i) {while (!pq.isEmpty() pq.peek()[1] i - k) {// 队头元素的索引已经超出了左边界直接移除队头元素已过期pq.poll();}pq.offer(new int[]{nums[i], i});ans[j] pq.peek()[0];}return ans;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n l o g k ) O(nlogk) O(nlogk) 其中 n n n 为数组中元素的个数 k k k是窗口的大小
搜索二维矩阵II
题目 原题链接240.搜索二维矩阵II 题解 解法一暴力枚举能过 class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int[] row : matrix) {for (int element : row) {if (element target) {return true;}}}return false;}
}复杂度分析 时间复杂度 O ( m n ) O(mn) O(mn)空间复杂度 O ( 1 ) O(1) O(1) 其中m是行n是列 解法二二分查找 二分查找的简单应用这里就不展开讲了唯一需要注意的就是边界问题对于边界问题的判断实在不会判断的有两种选择一种是直接举例列出边界条件一种是记口诀像这种经典的算法一般都有前辈总结的口诀但是我还是比较推荐使用距离列出边界条件记忆口诀这个东西太死了失去了算法本身的意义算法不是为了死记硬背而是在于理解 此外和这个题目相似的题还有很多可以直接搜索关键词二分查找 /*** author ghp* title*/
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int row matrix.length;for (int i 0; i row; i) {Integer result binarySearch(matrix[i], target);if (result ! null) {return true;}}return false;}private Integer binarySearch(int[] arr, int target) {int l 0, r arr.length-1;while (l r) {int mid (r - l) / 2 l;if (target arr[mid]) {return mid;} else if (target arr[mid]) {r mid - 1;} else {l mid 1;}}return null;}
}复杂度分析 时间复杂度 O ( m l o g n ) O(mlogn) O(mlogn)空间复杂度 O ( 1 ) O(1) O(1) 其中 n n n 为数组中元素的个数 解法三Z字形查找 这个解法来自LeetCode官网真TM强没想到啊啊啊啊 核心思路充分利用层与层之间的排序关系从右上角开始不断比较当前坐标的值和目标值缩小搜索范围每一次比较都能缩小一行或一列的数据 PS能画一个动图就好了我相信大家一看就懂大家脑补一下吧画图太费时间了这个解法理解起来并不难就是想不到啊 class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length, n matrix[0].length;int row 0, col n - 1;while (row m col 0) {if (matrix[row][col] target) {return true;}if (matrix[row][col] target) {// 目标值比当前坐标值要小则向左逼近--col;} else {// 目标值比当前坐标值要大则向下逼近row;}}return false;}
}复杂度分析 时间复杂度 O ( m n ) O(mn) O(mn)每次都会缩小一行或一列的数据所以最坏情况时间复杂度是 O ( m n ) O(mn) O(mn)也就是目标值在左下角空间复杂度 O ( 1 ) O(1) O(1) 其中m是行n是列
