1、滑动窗口最大值hot题目239. 滑动窗口最大值 - 力扣LeetCode分析①暴力解法左右双指针遍历 n-k1 个窗口。每个窗口都要找到最大值遍历 k 个数字。时间复杂度O(kn) (n-k1)*k空间复杂度O(1)②单调性队列我们能找到一个单调性规律如果新元素窗口中的元素那么窗口中的较小值必定不是最大值只要新元素在较小值都不会是新元素出窗口了较小值也必定出窗口了所以也不会是都需要删除直到窗口中元素新元素或者没有比新元素大的。因此这个窗口必满足单调递减窗口首元素必定是窗口中最大值。因为要频繁获取窗口首删除出窗口元素、获取最大值、尾元素删除较小值我们使用双端队列。因为我们需要判断队首元素是否在窗口范围内所以队列元素不能存元素值而存 index队首元素index不能≤ i - k。时间复杂度O(n) 遍历一次数组即可。空间复杂度O(k) 队列一直保持其中的元素都是窗口中的元素。代码class Solution { public int[] maxSlidingWindow(int[] nums, int k) { DequeInteger queue new LinkedList(); // 双端队列 Integer n nums.length; int[] retMax new int[n-k1]; // 构造第一个窗口 for(int i 0; i k; i) { // 窗口内存在元素且新元素比窗口内元素大就一直删除队尾 while(!queue.isEmpty() nums[i] nums[queue.peekLast()]) queue.pollLast(); queue.offerLast(i); // 新元素下标入队列 } // 队首元素就是窗口内最大值的下标 retMax[0] nums[queue.peekFirst()]; // 遍历剩下的元素进一次窗口出一次窗口 for(int i k; i n; i) { while(!queue.isEmpty() nums[i] nums[queue.peekLast()]) queue.pollLast(); queue.offerLast(i); // 删去不符合窗口范围的元素 while(queue.peekFirst() i-k) queue.pollFirst(); // 获取队首最大值下标 retMax[i-k1] nums[queue.peekFirst()]; } return retMax; } }2、搜索插入位置hot题目35. 搜索插入位置 - 力扣LeetCode分析排序数组、要求时间复杂度O(logn)二分查找。如果数组中没有查找值找第一个大于插入值的位置分为小于 t 的值lex1和大于 t 的值保留最左端 rix。就是查找左端点没找到左端点就是第一个比查找值大的值找到了左端点就是第一个查找值。特殊情况数组里全是小于 t 的数那么退出循环时leftright 指向最后一个数插入位置应该在其后一位。left。代码class Solution { public int searchInsert(int[] nums, int target) { int left 0, right nums.length-1; while(left right) { int mid left(right-left)/2; if(nums[mid] target) left mid1; else rightmid; } if(nums[left] target) left; return left; } }3、寻找旋转排序数组中的最小值hot题目153. 寻找旋转排序数组中的最小值 - 力扣LeetCode分析旋转后数组的分布代码class Solution { public int findMin(int[] nums) { int left 0, right nums.length-1; int t nums[right]; while(left right) { int mid left(right-left)/2; if(nums[mid] t) leftmid1; else rightmid; } return nums[left]; } }4、搜索二维矩阵hot题目74. 搜索二维矩阵 - 力扣LeetCode分析就是朴素二分查找只不过要把一维坐标映射为二维坐标来获取矩阵元素值。代码class Solution { // 把一维坐标映射为二维坐标 public boolean searchMatrix(int[][] matrix, int target) { int left 0, right matrix.length * matrix[0].length-1; int n matrix[0].length; while(left right) { int mid left(right-left)/2; if(matrix[mid / n][mid % n] target) leftmid1; else if(matrix[mid / n][mid % n] target) rightmid-1; else return true; } return false; } }5、搜索二维矩阵Ⅱhot题目240. 搜索二维矩阵 II - 力扣LeetCode分析以右上角为分界点 mid其行它是最大值其列它是最小值。若 mid target行增加若 mid target列减小。(x,y) 越界则未找到。代码class Solution { public boolean searchMatrix(int[][] matrix, int target) { int row 0, col matrix[0].length-1; while(row matrix.length col 0) { int mid matrix[row][col]; if(mid target) row; else if(mid target) col--; else return true; } return false; } }