• 基于数组结构刷题

    目录

    双指针用法

    26删除有序数组的重复项

     27移除元素​编辑

    283移动0

    左右指针

    334反转字符串

    Offer 57和为S的两个数字

    数组技巧之前缀和 

    二维矩阵中的前缀和

    offer66构建乘积

    560. 和为 K 的子数组

    双指针用法

    26删除有序数组的重复项

    • 这道题就很能体现数组的特性，我们找到数组是连续存储的，如果你想删除数组的一个元素，那么你必须去让这个元素之后的所有元素去往前覆盖一个元素，所以这道题，让我们去返回剩余元素的长度，其实并不是真的像链表那种将元素之间的连接断开 
    • 这题的思路就是双指针，我们用一个指针指向第一个元素，另一个也指向第一个元素，第一个元素是用来指向无序元素的最后一个索引，另一个指针来判断是否是重复的元素

    1. class Solution {
    2.   public int removeDuplicates(int[] nums) {
    3.         int n1=0;
    4.         int n2=0;
    5.         while (n2
    6.             if (nums[n1]==nums[n2]){
    7.                 n2++;
    8.             }else {
    9.                 n1++;
    10.                 nums[n1]=nums[n2];
    11.                 n2++;
    12.             }
    13.         }
    14.         return n1+1;
    15.     }
    16. }

    对比链表的数据结构

    •  链表我们需要通过next这种连接来遍历链表，其删除节点也非常简单，只需要断开相应的连接即可，这就是基于不同的数据结构，有不同的解决方法

    1. ListNode deleteDuplicates(ListNode head) {
    2.     if (head == null) return null;
    3.     ListNode slow = head, fast = head;
    4.     while (fast != null) {
    5.         if (fast.val != slow.val) {
    6.             // nums[slow] = nums[fast];
    7.             slow.next = fast;
    8.             // slow++;
    9.             slow = slow.next;
    10.         }
    11.         // fast++
    12.         fast = fast.next;
    13.     }
    14.     // 断开与后面重复元素的连接
    15.     slow.next = null;
    16.     return head;
    17. }

     27移除元素

    1. class Solution {
    2.   public int removeDuplicates(int[] nums) {
    3.         int n1=0;
    4.         int n2=0;
    5.         while (n2
    6.             if (nums[n1]==nums[n2]){
    7.                 n2++;
    8.             }else {
    9.                 n1++;
    10.                 nums[n1]=nums[n2];
    11.                 n2++;
    12.             }
    13.         }
    14.         return n1+1;
    15.     }
    16. }

    283移动0

    1. class Solution {
    2.    public void moveZeroes(int[] nums) {
    3.             //其实就是变形了一下，将0的元素全删除,留下前面的都是不为0的元素，把数组剩余的空间值都赋值为0
    4.           int p= remove(nums,0);
    5.         for (int i = p; i 
    6.             nums[i]=0;
    7.         }
    8.     }
    9.  
    10.     private int remove(int[] nums, int i) {
    11.         int slow=0;
    12.         int fast=0;
    13.         while (fast
    14.             if (nums[fast]!=0){
    15.                 nums[slow]=nums[fast];
    16.                 fast++;
    17.                 slow++;
    18.             }else {
    19.                 fast++;
    20.             }
    21.         }
    22.         return slow;
    23.     }
    24. }

    左右指针

    334反转字符串

    1. class Solution {
    2.        public void reverseString(char[] s) {
    3.         int left=0;
    4.         int right=s.length-1;
    5.         while (left
    6.             char temp=s[left];
    7.             s[left]=s[right];
    8.             s[right]=temp;
    9.             left++;
    10.             right--;
    11.         }
    12.     }
    13.  
    14.  
    15. }

    Offer 57和为S的两个数字

    1. class Solution {
    2.   public int[] twoSum(int[] nums, int target) {
    3.             int left=0;
    4.             int right=nums.length-1;
    5.             while (left
    6.                 if (nums[left]+nums[right]==target){
    7.                     int []arr={nums[left],nums[right]};
    8.                     return arr;
    9.                 }else if (nums[left]+nums[right]>target){
    10.                     right--;
    11.                 }else {
    12.                     left++;
    13.                 }
    14.             }
    15.             return null;
    16.     }
    17. }

    •  判断一个回文串，我们是通过从中间分开，看后面那一部分的逆序和前面一部分是否相同
    • 但是找一个回文串，我们应该从中间结点，然后向两端去判断加两个字符是否还是回文串，但是难点是我们知道回文串可能是偶数也可能是奇数个节点，我们可以通过一次传入两个节点，作为其中间节点，如果是奇数个节点，那么我们把中间节点传入两遍
    • 我们遍历字符串，将每一个节点，或者每两个节点作为中心节点，然后找出最长的回文字符串
    1. class Solution {
    2.     public String longestPalindrome(String s) {
    3.         String res="";
    4.         for (int i = 0; i < s.length(); i++) {
    5.             String str1=findPalindrome(s,i,i);//找奇数个的节点回文串
    6.             String str2=findPalindrome(s,i,i+1);//找偶数个节点的回文串
    7.             res=str1.length()>res.length()?str1:res;
    8.             res=str2.length()>res.length()?str2:res;
    9.         }
    10.         return res;
    11.     }
    12.  
    13.     private String findPalindrome(String s, int left, int right) {
    14.         while (left>=0&&right
    15.             left--;
    16.             right++;
    17.         }
    18.         return s.substring(left+1,right);//substring是左闭右开的
    19.     }
    20. }

    数组技巧之前缀和 

    一维数组前缀和

    前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。

    如何建立前缀和数组 

    • 前缀和数组的构造，其新数组的大小比nums大1，其preSum[0]==nums[0],preSum[i]=preSum[i-1]+nums[i-1]
    • preSum[i]表示nums[0]到nums[i-1]的之和
    1. /* 输入一个数组，构造前缀和 */
    2.     public NumArray(int[] nums) {
    3.         // preSum[0] = 0，便于计算累加和
    4.         preSum = new int[nums.length + 1];
    5.         // 计算 nums 的累加和
    6.         for (int i = 1; i < preSum.length; i++) {
    7.             preSum[i] = preSum[i - 1] + nums[i - 1];
    8.         }
    9.     }

    前缀和的作用

    • 看这个 preSum 数组，如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。
    1. class NumArray {
    2.  
    3.     int preNum[];
    4.     public NumArray(int[] nums) {
    5.         //根据nums来构造前缀和数组
    6.          preNum=new int[nums.length+1];
    7.         preNum[0]=0;//因为preNum[i]表示num[i-1]到num[0]的之和
    8.         for (int i = 1; i <=nums.length; i++) {
    9.             preNum[i]=preNum[i-1]+nums[i-1];
    10.         }
    11.     }
    12.  
    13.     public int sumRange(int left, int right) {
    14.             return preNum[right+1]-preNum[left];
    15.     }
    16. }
    17.  
    18. /**
    19.  * Your NumArray object will be instantiated and called as such:
    20.  * NumArray obj = new NumArray(nums);
    21.  * int param_1 = obj.sumRange(left,right);
    22.  */

    二维矩阵中的前缀和

     

    • 我们知道perNum[i][j]表示以num[i][j]为右下角，num[0][0] 为左下角，这个区间的所有元素之和

    构造前驱二维数组

    1.  int row=matrix.length;
    2.         int column=matrix[0].length;
    3.         preNum=new int[row+1][column+1];//表示matrix[i-1][j-1]的到[0][0]的总的元素之和
    4.         for (int i = 1; i <=row ; i++) {
    5.             for (int j = 1; j <=column; j++) {
    6.                 preNum[i][j]=preNum[i-1][j]+preNum[i][j-1]+matrix[i-1][j-1]-preNum[i-1][j-1];
    7.             }
    8.         }
    • 对于preNum[i][j],我们知道perNum[i][j]表示以num[i][j]为右下角，num[0][0] 为左下角，这个区间的所有元素之和,所以对于一个preNum[i][j]新添加的元素是matrix[i-1][j-1].那么对于构造
    1. class NumMatrix {
    2.  
    3.     int preNum[][];
    4.     public NumMatrix(int[][] matrix) {
    5.         if (matrix==null){
    6.             return;
    7.         }
    8.         int row=matrix.length;
    9.         int column=matrix[0].length;
    10.         preNum=new int[row+1][column+1];//表示matrix[i-1][j-1]的到[0][0]的总的元素之和
    11.         for (int i = 1; i <=row ; i++) {
    12.             for (int j = 1; j <=column; j++) {
    13.                 preNum[i][j]=preNum[i-1][j]+preNum[i][j-1]+matrix[i-1][j-1]-preNum[i-1][j-1];
    14.             }
    15.         }
    16.     }
    17.  
    18.     public int sumRegion(int row1, int col1, int row2, int col2) {
    19.          return preNum[row2+1][col2+1]-preNum[row1][col2+1]-preNum[row2+1][col1] +preNum[row1][col1];
    20.     }
    21. }
    22.  
    23. /**
    24.  * Your NumMatrix object will be instantiated and called as such:
    25.  * NumMatrix obj = new NumMatrix(matrix);
    26.  * int param_1 = obj.sumRegion(row1,col1,row2,col2);
    27.  */

    offer66构建乘积

    • 这道题的难点就是在于怎么去不用除法，我们的主要思路就是通过得到一个数的前面数据的乘积，和后面数据的乘积，这样我们就能得到其没有这个数据的乘积
    • 这两个数据的求法就是前缀和的类似求法，只是要注意其下标

    1. class Solution {
    2.          public int[] constructArr(int[] a) {
    3.         if (a==null||a.length==0){
    4.             return a;
    5.         }
    6.         //这道题要用两次前缀乘积得到数据
    7.         int prev[] = new int[a.length + 1];
    8.         int last[] = new int[a.length + 1];
    9.         prev[0] = 1;
    10.         last[a.length] = 1;
    11.         for (int i = 1; i <= a.length; i++) {
    12.             prev[i] = prev[i - 1] * a[i-1];
    13.         }
    14.         for (int i = a.length - 1; i >= 0; i--) {
    15.             last[i] = last[i + 1] * a[i];
    16.         }
    17.         int B[] = new int[a.length];
    18.  
    19.         B[a.length-1]=prev[a.length-1];
    20.         for (int i = 0; i 1; i++) {
    21.             B[i] = prev[i] * last[i + 1];
    22.         }
    23.         return B;
    24.     }
    25.  
    26. }

    560. 和为 K 的子数组

    1. package algorithm.Arrays.PrefixSum;
    2.  
    3. public class Test560 {
    4.     public int subarraySum(int[] nums, int k) {
    5.         int count=0;
    6.         int prev[]=new int[nums.length+1];
    7.         prev[0]=0;
    8.         //构造前缀和数组
    9.         for (int i = 1; i <=nums.length; i++) {
    10.             prev[i]=prev[i-1]+nums[i-1];
    11.         }
    12.         for (int left = 0; left 
    13.             for (int right = left; right < nums.length; right++) {
    14.                 //[left,right]
    15.                 //通过前缀和来计算[right,left]的区间之和
    16.                 if (prev[right+1]-prev[left]==k){
    17.                     count++;
    18.                 }
    19.             }
    20.         }
    21.         return count;
    22.     }
    23. }
    • 这种就是最普通的方法，但是这种方法会超时
    • 我们这里只是需要找数为k的区间，我们用map记录每个前缀和的，如果每遇到一个前缀和为i的值，我们就去map中找是否有前缀和为i-k的存在，如果有，就将前缀和的为i-k的数据加到统计次数中
    1. class Solution {
    2.             public int subarraySum(int[] nums, int k) {
    3.         int count=0;
    4.         int prev[]=new int[nums.length+1];
    5.         prev[0]=0;
    6.         //构造前缀和数组
    7.         for (int i = 1; i <=nums.length; i++) {
    8.             prev[i]=prev[i-1]+nums[i-1];
    9.         }
    10.         Map map=new HashMap<>();
    11.         for (int i = 0; i < prev.length; i++) {
    12.             // 如果有与当前prefixSum[i]的差为k的，则加上它的个数
    13.             //因为两个前缀和相差为k,说明是这个区间的值为k
    14.             count+=map.getOrDefault(prev[i]-k,0);
    15.             //统计前缀和的个数
    16.             map.put(prev[i],map.getOrDefault(prev[i],0 )+1);
    17.         }
    18.         return count;
    19.     }
    20.  
    21.  
    22.  
    23. }

    二维数组的花式遍历 

    1. class Solution {
    2.           public int[] spiralOrder(int[][] matrix) {
    3.         int res[] = new int[0];
    4.         if (matrix==null||matrix.length==0){
    5.             return res;
    6.         }
    7.         int row=matrix.length;
    8.         int column=matrix[0].length;
    9.         int upper_bound=0;//上界
    10.         int lower_bound=row-1;//下界
    11.         int left_bound=0;//左界
    12.         int right_bound=column-1;
    13.         int count=0;
    14.         res=new int[row*column];
    15.         while (count
    16.             //先从最上侧从左走向右 怎么保证还有路可以走 就是上边界(大于等于)下边界
    17.             if (upper_bound<=lower_bound){
    18.                 for (int i = left_bound; i <=right_bound ; i++) {
    19.                     res[count]=matrix[upper_bound][i];
    20.                     count++;
    21.                 }
    22.                 upper_bound++;
    23.                 //从最左侧走到最右侧 说明我们走完了一行,就需要将上边界++
    24.             }
    25.             //先从最右侧从上往下走 怎么保证还有路可以走 就是左边界(小于等于)右边界
    26.             if (left_bound<=right_bound){
    27.                 for (int i = upper_bound; i <=lower_bound ; i++) {
    28.                     res[count]=matrix[i][right_bound];
    29.                     count++;
    30.                 }
    31.                 right_bound--;
    32.                 //从最右侧从上走到下 说明我们走完了一列,就需要将右边界--
    33.             }
    34.             //从最下侧 从左走到右,如何保证有地方可以走
    35.             if (upper_bound<=lower_bound){
    36.                 for (int i = right_bound; i >=left_bound ; i--) {
    37.                     res[count]=matrix[lower_bound][i];
    38.                     count++;
    39.                 }
    40.                 lower_bound--;
    41.                 //从最左侧走到最右侧 说明我们走完了一行,就需要将上边界++
    42.             }
    43.             //先从最左侧从下往上走 怎么保证还有路可以走 就是左边界(小于等于)右边界
    44.             if (left_bound<=right_bound){
    45.                 for (int i = lower_bound; i >=upper_bound ; i--) {
    46.                     res[count]=matrix[i][left_bound];
    47.                     count++;
    48.                 }
    49.                 //从最右侧从下走到上 说明我们走完了一列,就需要将右边界--
    50.                 left_bound++;
    51.             }
    52.         }
    53.         return res;
    54.     }
    55.  
    56. }

     48旋转图像

    • 先将数组按照斜对角线交换，然后将每一行进行逆序

    1. class Solution {
    2.        public void rotate(int[][] matrix) {
    3.         int n=matrix.length;
    4.         for (int i = 0; i < n; i++) {
    5.             for (int j = i; j 
    6.                 int temp=matrix[i][j];
    7.                 matrix[i][j]=matrix[j][i];
    8.                 matrix[j][i]=temp;
    9.             }
    10.         }
    11.         for (int []arr:matrix) {
    12.             int left=0;
    13.             int right=n-1;
    14.             while (left
    15.                 int temp=arr[left];
    16.                 arr[left]=arr[right];
    17.                 arr[right]=temp;
    18.                 left++;
    19.                 right--;
    20.             }
    21.         }
    22.     }
    23.  
    24. }

    滑动窗口的应用 

    滑动窗口的核心框架

    1. /* 滑动窗口算法框架 */
    2. void slidingWindow(string s) {
    3.     HashMap<char, int> window;
    4.     
    5.     int left = 0, right = 0;
    6.     while (right < s.size()) {
    7.         // c 是将移入窗口的字符
    8.         char c = s.charAt(i);
    9.         // 增大窗口
    10.         right++;
    11.         // 进行窗口内数据的一系列更新
    12.         ...
    13.  
    14.         /*** debug 输出的位置 ***/
    15.         printf("window: [%d, %d)\n", left, right);
    16.         /********************/
    17.         
    18.         // 判断左侧窗口是否要收缩
    19.         while (window needs shrink) {
    20.             // d 是将移出窗口的字符
    21.             char d = s.charAt(i);
    22.             // 缩小窗口
    23.             left++;
    24.             // 进行窗口内数据的一系列更新
    25.             ...
    26.         }
    27.     }
    28. }
    • 滑动窗口的最大应用就是子串问题

    • 我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

      PS：理论上你可以设计两端都开或者两端都闭的区间，但设计为左闭右开区间是最方便处理的。因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素，但只要让 right 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。如果你设置为两端都开的区间，那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，那么初始区间 [0, 0] 就包含了一个元素。两种情况都会给边界处理带来不必要的麻烦。

      2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

      3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

      4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

    76最小覆盖字串

    1. package algorithm.Arrays.slideWindow;
    2.  
    3. import java.util.HashMap;
    4.  
    5. public class Test76 {
    6.     public String minWindow(String s, String t) {
    7.         HashMap window=new HashMap<>();//滑动窗口
    8.         HashMap need=new HashMap<>();
    9.         //need 用来存储我们需要的字符和对应的需要的字符的个数
    10.         for (int i = 0; i < t.length(); i++) {
    11.              char c=t.charAt(i);
    12.              need.put(c,need.getOrDefault(c,0)+1);
    13.         }
    14.         int left=0;
    15.         int right=0;
    16.         //区间的左闭右开的
    17.         int valid=0;//满足条件的字符个数
    18.         int start=0,len=Integer.MAX_VALUE;//用来确定符合条件的字符串
    19.         while (right
    20.             //c是即将要移入的字符
    21.             char c=s.charAt(right);
    22.             //右移 扩大窗口
    23.             right++;
    24.             //这一部分是模板，用于我们移动右指针,增大窗口
    25.             //-------------------------------------
    26.             if (need.containsKey(c)){
    27.                 window.put(c,window.getOrDefault(c,0)+1);
    28.                 if (window.get(c).equals(need.get(c))){
    29.                     valid++;
    30.                 }
    31.             }
    32.             //这一部分是因题目不同,对窗口内的数据进行更新(新填一个字符，可能要更新对应map（window）数据)
    33.             //-------------------------------------
    34.             while (valid==need.size()){
    35.                 //说明了当前我们的窗口的字符串已经满足了条件
    36.                 //以下用来更新左边的范围
    37.                 if (right-left
    38.                     start=left;
    39.                     len=right-left;
    40.                     //说明存在更短的窗口大小
    41.                 }
    42.                 
    43.                 //------------------
    44.                 //d是要移出去的字符
    45.                 char d=s.charAt(left);
    46.                 //将left这个字符从窗口移除
    47.                 left++;
    48.                 //满足条件,我们必须开始减少窗口的大小,这也滑动窗口的模板
    49.                 
    50.                 //-------------------
    51.                 if (need.containsKey(d)){
    52.                     //如果删除的这个字符是need里面的字符
    53.                     if (window.get(d).equals(need.get(d))){
    54.                         //如果现在窗口中这个字符的数量跟我们需要的字符数量一样,那么减去这个，这个字符就不满足要求了
    55.                         valid--;
    56.                     }
    57.                     window.put(d,window.getOrDefault(d,0)-1);
    58.                 }
    59.                 //减少一个数据，有可能会让我们对应的map(need)数据会变化，不同的题目会有不同的情况
    60.                 
    61.             }
    62.         }
    63.         return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    64.     }
    65. }
    • 首先套核心的滑动窗口套路，左闭右开的窗口区间,left从0开始，right从0开始
    • 当不满足条件的时候，首先一直让窗口变大（right++），直到满足了条件，当满足了条件，我们就一直减少窗口的大小（left--），直到不满足了条件，我们就继续让窗口变大，一直重复，直到right走到了数组的尽头
    • 不同的就是关于，如何去判断是否满足了条件，和记录我们要保留的数据，这道题的判断，是靠两个map,window来记录窗口中字符和其对应的个数，need来记录我们需要的字符和其对应的个数，用vaild来记录我们满足的字符的个数，如果vaild==need.length，说明满足条件，小于就不满足
    • 这里面有一个Java语法的注意点，就是Interger这是一个包装类，切回缓存频繁使用的数值，数值范围是-128到127，在次范围内会直接返回缓存值，如果超过了这个范围，会新new一个对象，不能用等于号，用equlas;
    1.  Integer a1 = 1234;
    2.         Integer a2 = 1234;
    3.         System.out.println(a1 == a2);//false
    4.         System.out.println(a1.equals(a2));//true
    5.  
    6.         Integer a3 = 123;
    7.         Integer a4 = 123;
    8.         System.out.println(a3 == a4);//true
    9.         System.out.println(a3.equals(a4));//true

    438找到字符串所有的字母异位词

    1. class Solution {
    2.        public List findAnagrams(String s, String p) {
    3.         List res=new LinkedList<>();//用于存储我们的结果
    4.         HashMap window=new HashMap<>();//窗口的存储的信息
    5.         HashMap need=new HashMap<>();
    6.         //存储需要的对应的信息
    7.         for (int i = 0; i < p.length(); i++) {
    8.             char c=p.charAt(i);
    9.             need.put(c,need.getOrDefault(c,0)+1);
    10.         }
    11.         int left=0;
    12.         int right=0;
    13.         //定义左右指针
    14.         int valid=0;//我们这里维护的应该是一个定长的区间，如果
    15.         while (right
    16.             char c=s.charAt(right);//当前我们要进行插入的字符
    17.             right++;
    18.             if (need.containsKey(c)){
    19.                 //这个字符是我们需要的
    20.                 window.put(c,window.getOrDefault(c,0)+1);
    21.                 if (need.get(c).equals(window.get(c))){
    22.                     valid++;
    23.                 }
    24.             }
    25.             while (right-left==p.length()){
    26.                 //当前窗口的大小等于了我们要找的字符串
    27.                 if (valid==need.size()){
    28.                     //因为我们这里要的是一个定长的结果 只能是abc bac这种
    29.                     //所以满足条件不一定可以,比如abcd就不行
    30.                     //所以在这个外面加了一个判断是当前窗口大小==需要字符串的长度
    31.                     res.add(left);
    32.                 }
    33.                 char d=s.charAt(left);//我们要减去的窗口的字符
    34.                 left++;
    35.                 //进行缩减窗口
    36.                 if (need.containsKey(d)){
    37.                     //减去的这个元素是我们需要的
    38.                     if (window.get(d).equals(need.get(d))){
    39.                         //当前元素的个数刚好是我们需要的，减去一个就不够了
    40.                         valid--;
    41.                     }
    42.                     window.put(d,window.get(d)-1);
    43.                 }
    44.             }
    45.         }
    46.         return res;
    47.     }
    48.  
    49. }
    • 由于这道题中 [left, right) 其实维护的是一个定长的窗口，窗口大小为 t.size()。因为定长窗口每次向前滑动时只会移出一个字符，所以可以把内层的 while 改成 if，效果是一样的

    1.     public int lengthOfLongestSubstring(String s) {
    2.         HashMap window=new HashMap<>();
    3.         int left=0;
    4.         int right=0;
    5.         int max=0;
    6.         while (right
    7.             char c=s.charAt(right);//我们要更新的字符
    8.             right++;
    9.             //窗口变大
    10.             //--------------------------------------------
    11.             window.put(c,window.getOrDefault(c,0)+1);//将这个数据放进去 数据处理
    12.             //--------------------------------------------
    13.             while (window.get(c)>1){
    14.                 //说明当前字符串不满足了要求了
    15.                 //窗口要减小
    16.                 char d=s.charAt(left);
    17.                 left++;
    18.                 //-----------------------
    19.                 window.put(d,window.get(d)-1);//数据处理
    20.             }
    21.             //----------------------------------------------
    22.             max=Math.max(right-left,max);
    23.         }
    24.         return max;
    25.     }

    239滑动窗口的最大值

    •  这道题，我们首先想到用优先级队列（堆）来解决问题，因为堆这种结构最大的功能就是k个元素中找到最大值，但是有一个致命的缺陷，我们窗口移动的时候，如果最左边的元素的这些里面最大的值（比如元素的 5 2 1 4）从5 2 1 到2 1 4，其中最大值应该是4，但是我们最移动的时候（堆中的元素从 5 2 1 变成 5 2 1 4），但是5并不是我们范围内的元素，但是堆没有这种功能，来判断是不是范围内元素，所以我们传入堆中的数据，传一个键值对，值和对应的索引
    1. class Solution {
    2.          public int[] maxSlidingWindow(int[] nums, int k) {
    3.         PriorityQueue<int[]> window=new PriorityQueue<>(new Comparator<int[]>() {
    4.             @Override
    5.             public int compare(int[] o1, int[] o2) {
    6.                 return o1[0]!=o2[0]?o2[0]-o1[0]:o2[1]-o1[1];
    7.             }
    8.         });
    9.         //将堆中先放入k个元素
    10.         for (int i = 0; i < k; i++) {
    11.             window.offer(new int[]{nums[i],i});
    12.         }
    13.         int []res=new int[nums.length-k+1];
    14.         res[0]=window.peek()[0];//取出当前堆中的最大元素
    15.         for (int i = k; i 
    16.             window.offer(new int[]{nums[i],i});
    17.             while (window.peek()[1]1){
    18.                 window.poll();
    19.                 //移除最大元素,但是不属于当前窗口的
    20.             }
    21.             res[i-k+1]= window.peek()[0];
    22.         }
    23.         return res;
    24.     }
    25.  
    26.  
    27.  
    28. }

    利用单调队列来实现

    1. class Solution {
    2.     class MonotonicQueue {
    3.         LinkedList dq = new LinkedList<>();
    4.         public void push(int n) {
    5.             while (!dq.isEmpty() && n > dq.getLast()) {
    6.                 dq.pollLast();
    7.             }
    8.             dq.addLast(n);
    9.             //通过删除一起比要添加数字要小的元素,形成一个递减的队列
    10.         }
    11.  
    12.         public int max() {
    13.             return dq.getFirst();
    14.             //第一个元素是最大值
    15.         }
    16.  
    17.         public void pop(int n) {
    18.             if (n == dq.getFirst()) {
    19.                 dq.pollFirst();
    20.             }
    21.         }
    22.     }
    23.     public int[] maxSlidingWindow(int[] nums, int k) {
    24.         MonotonicQueue window=new MonotonicQueue();
    25.         List res = new ArrayList<>();
    26.         for (int i = 0; i < nums.length; i++) {
    27.             if (i1){
    28.                 window.push(nums[i]);
    29.             }else {
    30.                 //窗口向前滑动一个大小
    31.                 window.push(nums[i]);
    32.                 res.add(window.max());
    33.                 window.pop(nums[i-k+1]);
    34.             }
    35.         }
    36.         // 需要转成 int[] 数组再返回
    37.         int[] arr = new int[res.size()];
    38.         for (int i = 0; i < res.size(); i++) {
    39.             arr[i] = res.get(i);
    40.         }
    41.         return arr;
    42.     }
    43. }
    •  首先利用队列这个结构，先进先出（我们可以实现每次让最先进来出去），为什么要变成单调的队列呢？因为我们要的是最大值，我们弄一个递减的队列，每次头都是最大值，我们去判断，如果队列的头的值是我们刚刚窗口最左边的值，我们可以将这个值删除，就不会影响我们向右移动，窗口左边的值影响我们取最大值

    入队操作push

    •  每次先将前面那些小于要添加的元素的值删除，这样就可以得到一个递增的队列

    关于删除，因为只能从头去删除，对于我们这道题，我们什么时候去删除队列的头元素呢

    •  我们知道，我们去移动窗口的时候，如果窗口最左边的数字等于我们当前窗口的最大值（单调队列的头节点），那么我们应该去删除头节点的值，如果最左边的数不是我们的最大值，就不需要去删除

     

  • 相关阅读:
    Java面试八股文宝典:初识数据结构-数组的应用扩展之HashTable
    MySQL -- mysql connect
    Python基础（七）：条件语句深入了解
    C#《原CSharp》第四回 人常见岁月更替 却难知人文相继
    Picasso学习
    【JavaScript】面试手撕节流
    C++中的深拷贝和浅拷贝
    掌握Python操作Word：从基础到高级全覆盖
    华为数通方向HCIP-DataCom H12-821题库(单选题：361-380）
    滚雪球学Java(09-3)：Java中的逻辑运算符，你真的掌握了吗？
  • 原文地址：https://blog.csdn.net/qq_50985215/article/details/126177379