• Leetcode《图解数据结构》刷题日志【第二周】（2022/10/24-2022/10/30）

    《图解数据结构》刷题日志【第二周】

    1. 剑指Offer 24.反转链表

    1.1 题目

       定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

   示例:
   输入: 1->2->3->4->5->NULL
   输出: 5->4->3->2->1->NULL

   限制：
   0 <= 节点个数 <= 5000

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    1.2 解题思路

    最简单的思路，设置一个数组，遍历两次链表，第一次遍历将链表节点的值存入数组，第二次遍历将数组中元素倒序覆盖链表元素。

    考虑到数组长度问题且数据倒序，使用栈更加方便。

    1.3 数据类型功能函数总结

     //链表相关操作
 ListNode.val;//取链表结点的值
 ListNode.next;//取链表节点的指针
 //栈相关操作
 Stack<> Stack_Name =new Stack<>();//定义一个空栈
 Stack.push(value);//元素入栈，存于栈顶
 Stack.pop();//顶部元素出栈

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    1.4 java代码

    /**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
//设定一个栈，存储元素，然后覆盖
class Solution {
   public ListNode reverseList(ListNode head) {
      Stack<Integer> stack=new Stack<Integer>(); 
      ListNode h=head;
      while(h!=null){
         stack.push(h.val);
         h=h.next;
      }
      h=head;
      while(h!=null){
         h.val=stack.pop();
         h=h.next;
      }
      return head;
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    1.5 进阶解法

    用栈来解题，得到的空间复杂度明显过高，还是要有点追求。

    官方题解里面提到了两种解法，首先是“双指针法”。
    官方题解里面的动画示范解释得非常清晰，主要就是使用两个指针cur和pre，cur从第一个节点、第二个节点一直到尾节点，而pre从尾部的null、第一个节点，第二个节点一直到尾节点；cur次都将自己的指针指向pre，从而实现链表逆转。而temp指针是一个临时指针，用来在cur和pre的指针变换中保留cur下一步要移动到的位置。
    双指针法的代码如下：

    /**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode reverseList(ListNode head) {
      //双指针
      ListNode cur=head,pre=null,temp;
      while(cur!=null){
         temp=cur.next;
         cur.next=pre;
         pre=cur;
         cur=temp;
      }
      return pre;
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    第二个解法是“递归法”，定义函数recur(px,py),在递归函数中边界条件是px为空，返回前驱指针py。
    递归部分则递归改变px.next以及px，用py的指针指向px，并且返回记录的头指针。
    但是感觉理解难度和时空复杂度并没有双指针法那么好，所以对这个算法没啥感觉。

    class Solution {
   public ListNode reverseList(ListNode head) {
      return recur(head, null);    // 调用递归并返回
   }
   private ListNode recur(ListNode cur, ListNode pre) {
      if (cur == null) return pre; // 终止条件
      ListNode res = recur(cur.next, cur);  // 递归后继节点
      cur.next = pre;              // 修改节点引用指向
      return res;                  // 返回反转链表的头节点
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    2. 剑指Offer 30.包含min函数的栈

    2.1 题目

      定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

  示例:
  MinStack minStack = new MinStack();
  minStack.push(-2);
  minStack.push(0);
  minStack.push(-3);
  minStack.min();   --> 返回 -3.
  minStack.pop();
  minStack.top();      --> 返回 0.
  minStack.min();   --> 返回 -2.

  提示：
  各函数的调用总次数不超过 20000 次

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    2.2 解题思路

    这一题主要是实现栈，这部分可以使用数组结构，首部表示栈底，尾部表示栈顶。

    但是这个栈里面能够以O(1)的时间复杂度查找到最小元素，因此还需要一个数据结构，空间换时间，这个数据结构最好能够做到记录最小元素的大小和位置并根据pop()和push()方法实时更新。

    因此设置两个数组结构，stackL用来实现栈，而minL用来实现min查找。

    min查找时，对minL的元素进行从小到大排序，并且给出最小元素的值。（不过排序这里应该也不是O（1）吧？）

    2.3 数据类型功能函数总结

     //ArrayList相关操作
 ArrayList<> AL_Name = new ArrayList<>();//定义一个数组
 ArrayList.add(element);//添加元素
 ArrayList.remove(index);//删除指定下标的元素
 ArrayList.get(index);//获得指定下标的元素值
 ArrayList.size();//获得数组大小
 ArrayList.indexOf(element);//查找元素的下标位置

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    2.4 java代码

    class MinStack {
   ArrayList<Integer> stackL;
   ArrayList<Integer> minL;//辅助min的查找
   //int min;
   /** initialize your data structure here. */
   public MinStack() {
      stackL =new ArrayList<Integer>();//头部--栈底，尾部--栈顶
      minL = new ArrayList<Integer>();//存储最小元素的位置
   }
 
   public void push(int x) {
      stackL.add(x);
      minL.add(x);
   }
 
   public void pop() {//从尾部取出元素并删除
      int size=stackL.size();
      if(size!=0){
         int ele=stackL.get(size-1);
         stackL.remove(size-1);
         int index=minL.indexOf(ele);
         minL.remove(index);
      }
   }
 
   public int top() {
      int size=stackL.size();
      if(size!=0){//空栈处理
         return stackL.get(size-1);
      }
      else{
         return -1;
      }
   }
 
   public int min() {
      //调用min的时间复杂度是O（1），不能使用一般的遍历方法，需要空间换时间
      Collections.sort(minL);
      return minL.get(0);
   }
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    2.5. 进阶解法

    实际上，因为minL在上述的解法里面只是一种“副本”，排序算法也不是O（1）的时间复杂度，因此最后运行的效果并不让人满意。
    运行结果
    官方题解里也用到了辅助栈，但是不同于在min()中使用排序来操作，而是始终确保最小元素为栈顶元素。

    维护minL的实际操作在pop()和push()中实现。
    - pop()中，将元素放入stackL中，维护minL，m
    - 如果minL为空，说明是空栈新加入元素，直接放入minL中，
    - 如果minL不为空，则栈顶记录着当前的最小元素，如果新加入的元素比栈顶还小，则压入栈中。
    - push()中，元素弹出stackL栈，但是还需要考虑弹出的元素是不是最小元素（minL的栈顶），如果是的话，minL中也需要弹出栈顶元素。
    - top()中查找stackL中的栈顶元素
    - min()中查找minL中的栈顶元素

    实际上这种思路我曾经想到过，也就是用minL栈来存储最小元素，栈顶永远是最小元素，但是我的想法是通过pop()中的相关操作能够让所有元素在minL中实现排序。这样的话，原本就不是最小元素的数字很难在minL中进行适当的插入。

    然而，官方题解中直接忽略了非最小元素的其他元素，不考虑这些元素在minL中的排列。

    仔细想了一下，比如说例子11 9 10 7 3 5,stackL=[11,9,10,7,3,5],minL=[11,9,7,3]。当10还存在于stackL中的时候，必然能够保证9是栈中的最小元素，因为两者之间存在一个先后顺序，只有10出栈了才有可能影响到9的存在。因此，是可以忽略非最小元素的其他元素的。

    而在代码的数据结构选择中，我一开始选择的是ArrayList,也就是一般的数组结构，但是不定长。而实现栈的时候通常选择LinkedList结构或者Stack结构，代码部分我们选择LinkedList来实现栈操作。用Stack实现另一个栈很奇怪，而且在实际的性运行中，Stack效率并不高
    > Java中Stack的push、pop、peek操作都用synchronized关键字修饰，影响效率。而且Java也提供了更好的同步方案，是不建议使用Stack的（From：Zhxy）

    相关数据结构的操作：

    //LinkedList的相关操作
LinkedList<> LL_Name = new LinkedList<>();//定义一个链表
LinkedList.addLast(element);//在尾部添加元素，相当于入栈
LinkedList.removeLast();//在尾部删除元素，相当于出栈
LinkedList.getLast();//获取尾部元素的值，相当于栈的top()函数
LinkedList.size();//获得链表中节点的数目，即数据结构的范围
//LinkedList还有对应的addFirst()/removeFirst()/getFirst()等操作，也可以用在队列的实现中

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    代码如下（使用LinkedList结构）：

    class MinStack {
   LinkedList<Integer> stackL;
   LinkedList<Integer> minL;//辅助min的查找

   /** initialize your data structure here. */
   public MinStack() {
      stackL =new LinkedList<Integer>();//头部--栈底，尾部--栈顶
      minL = new LinkedList<Integer>();//存储最小元素的位置
   }
 
   public void push(int x) {
     stackL.addLast(x);
     if(minL.size()==0 || x <= minL.getLast()){//等于是为了避免push的时候出错
         minL.addLast(x);//在尾部添加目前的最小值
     }
   }
 
   public void pop() {//从尾部取出元素并删除
      if(stackL.size()!=0){
         int ele=stackL.getLast();
         stackL.removeLast();
         if(ele==minL.getLast()){
             minL.removeLast();
         }
      }
   }
 
   public int top() {
      if(stackL.size()!=0){//空栈处理
         return stackL.getLast();
      }
      else{
         return -1;
      }
   }
 
   public int min() {
      //调用min的时间复杂度是O（1），不能使用一般的遍历方法，需要空间换时间
      return minL.getLast();
   }
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    运行结果如下：
    运行结果

    和一开始的思路相比，时间性能的提升还是很明显的：
    运行结果

    3. 剑指Offer 35.复杂链表的复制

    3.1 题目

    运行结果

    3.2 解题思路

    个人思路：两次遍历旧链表，第一次遍历新建结点、连接next关系、将每个节点的random关系存入一个数据结构（数组或者队列）中，第二次遍历的时候通过遍历数据结构和新链表，连接random关系。

    实际上Node应该是一个链表节点的指针，因此将random关系存入的数据结构如果只是一个指针数组的话，指向的依然是旧节点的内存地址，所以这里需要用到新旧节点共同存储，在官方题解中使用的是HashMap这个数据结构，这样使用HashMap.get(旧节点指针)能够获得新节点指针。

    3.3 数据类型功能函数总结

     //HashMap相关操作
 HashMap<type,type> HM_Name = new HashMap<type,type>();//定义
 HashMap.put(key,value);//添加键值对
 HashMap.get(key);//通过关键字key查找对应的值value
 //链表相关操作
 Class Node {//定义
    int val;
    Node next;
    public Node(int val){
       this.val=val;
       this.next=null;
    }
 }
 Node node=new Node(value);//新建链表节点
 Node.val;Node.next;//取出结构体中的变量

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    3.4 java代码

    /*
// Definition for a Node.
class Node {
   int val;
   Node next;
   Node random;

   public Node(int val) {
      this.val = val;
      this.next = null;
      this.random = null;
   }
}
*/
//1.节点如何创建？Node 节点名=new Node(value);
//2.如何表示随机？数组存储——后改成HashMap存储
//3.如何遍历链表？cur=cur.next;
//4.Node是一个指针还是一个结构体？一个指针
class Solution {
   public Node copyRandomList(Node head) {
      if(head==null){return head;}
 
      Node pre=new Node(head.val);
      Node re=pre;
      Node cur=head.next;//遍历旧数组
      HashMap<Node,Node> rdm=new HashMap<Node,Node>();
      rdm.put(head,pre);
      while(cur!=null){//第一次遍历：创建新节点，连接next部分，random存于数组中
         Node node=new Node(cur.val);
         rdm.put(cur,node);
         pre.next=node;
         pre=node;
         cur=cur.next;
      }
      pre=re;
      cur=head;
      while(cur!=null){//第二次遍历，连接random部分
         rdm.get(cur).random=rdm.get(cur.random);
         cur=cur.next;
      }
      return re;    
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    3.5 进阶解法

    上述的思路实际上类似官方题解中的第一种解法。运行结果如下所示
    运行结果

    • 第一种解法比起个人解法更加简洁，第一次遍历的时候只是新建节点，将新旧节点存储在HashMap中，第二次遍历的时候才连接next和random关系。
    /*
// Definition for a Node.
class Node {
   int val;
   Node next;
   Node random;

   public Node(int val) {
      this.val = val;
      this.next = null;
      this.random = null;
   }
}
*/

class Solution {
   public Node copyRandomList(Node head) {
      if(head==null){return head;}
 
      Map<Node,Node> rdm=new HashMap<>();
      Node cur=head;//遍历旧数组
     
      while(cur!=null){//第一次遍历：创建新节点，连接next部分，random存于数组中
         Node node=new Node(cur.val);
         rdm.put(cur,node);
         cur=cur.next;
      }
      cur=head;
      while(cur!=null){//第二次遍历，连接random部分
         rdm.get(cur).next=rdm.get(cur.next);
         rdm.get(cur).random=rdm.get(cur.random);
         cur=cur.next;
      }
      return rdm.get(head);    
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    运行结果如下所示：
    运行结果
    可以看出两个解法的时空复杂度几乎一样。

    • 第二种解法：拼接+拆分
      实际上这种解法和第一种解法有类似之处，那就是将新旧节点混在一起，通过旧节点查找新节点。

      解法中用到了三次遍历：

      第1次遍历：构建新节点，将新旧节点交叉连接在一起，next关系已经间接存在。

      第2次遍历：通过旧节点构建新节点之间的random关系

      第3次遍历：拆分新旧链表。

      class Solution {
public Node copyRandomList(Node head) {
   if(head==null){return head;}

   Node cur=head;
   while(cur!=null){//第一次遍历
       Node node=new Node(cur.val);
       node.next=cur.next;
       cur.next=node;
       cur=node.next;
   }   
   cur=head;
   while(cur!=null){
       if(cur.random!=null){
           cur.next.random = cur.random.next;//核心,结合题解动画理解
       }
       cur=cur.next.next;
   }
   Node nhead=head.next, pre=head;
   cur=nhead;
   while(cur.next!=null){
       pre.next=pre.next.next;
       cur.next=cur.next.next;
       cur=cur.next;
       pre=pre.next;
   }
   pre.next=null;
   return nhead;
}
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30

      运行结果如下所示：
      运行结果

    3.6.疑惑点

      这题我觉得很奇怪的一点就是链表结点Node的结构体定义。

    • 1
    class Node {
   int val;
   Node next;
   Node random;

   public Node(int val) {
      this.val = val;
      this.next = null;
      this.random = null;
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    这里的Node指针直接用的是Node类型，而在C语言中，这里应该写Node*

    4. 剑指Offer 58-II.左旋转字符串

    4.1 题目

    字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
   输入: s = "abcdefg", k = 2
   输出:?"cdefgab"

示例 2：
   输入: s = "lrloseumgh", k = 6
   输出:?"umghlrlose"

限制：
   1 <= k < s.length <= 10000

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    4.2 解题思路

    最简单的思路可以是从index=n的下标位置选择字符存入StringBuilder中，遍历范围是n~size-1,然后第二次遍历选择前半部分的数据存入结果变量中，遍历范围是0~n-1.

    另外还有一种巧妙且经典的做法，那就是通过n将字符串分为两个部分，两个部分分别反转一次，合并之后再次反转一次，经过这样的三次反转之后也能得到左旋的结果。

    值得注意的是，String类型的字符串是不可修改的，因此，如果想要进行字符串的反转和分割，我们将两部分字符串存储在StringBuilder类型中，并使用java自带的功能函数StringBuilder.reverse()来实现字符串的反转。

    4.3 数据类型功能函数总结

    //String相关操作
String s_name = "";//定义一个空字符串
String.length();//获得当前字符串的长度
String.charAt(index);//获得字符串中下标为index的字符
for(int i=0;i<String.length();i++){}//字符串的遍历
String.substring(start_index,end_index);//获取字符串的子串，范围是[start_index,end_index);
String1 + String2;//两个字符串进行拼接，但是String的拼接还是会使用StringBuilder或者StringBuffer类型来实现，因此频繁使用这种操作会导致代码效率低下
//StringBuilder相关操作
StringBuilder SB_Name=new StringBuilder();//定义一个空字符串
StringBuilder.toString();//将StringBuilder类型转化为String类型
StringBuilder.append(char/String);//将字符或者字符串添加到字符串中
StringBuilder.reverse();//将字符串进行反转，返回反转之后的结果

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    4.4 java代码

    class Solution {
   //有个很经典的做法，k=n将字符串分成两部分，然后两部分分别反转，合并之后再反转一次
   public String reverseLeftWords(String s, int n) {
      StringBuilder re1 = new StringBuilder();
      StringBuilder re2 = new StringBuilder();
      int i=0;
      for(i=0;i<n;i++){
         re1.append(s.charAt(i));
      }
      for(i=n;i<s.length();i++){
         re2.append(s.charAt(i));
      }
      re1.reverse();
      re2.reverse();
      re1.append(re2.toString());
      re1.reverse();
      return re1.toString();
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    4.5 另解

    上述三次反转的java代码的运行结果如下图所示：
    运行结果

    官方题解里面适用于java的方式主要就是切片法，也就是分别遍历后半部分和前半部分，将数据存储在结构体中

    实际上反思一下，这样的做法确实比上文的做法要好，因为re1和re2的构建还是需要逐个字符的移动，因此三次反转用在这里还是有点"画蛇添足"的感觉。

    使用StringBuilder 的切片法

    class Solution {
   public String reverseLeftWords(String s, int n) {
      StringBuilder re = new StringBuilder();
      int i=0;
      
      for(i=n;i<s.length();i++){
         re.append(s.charAt(i));
      }
      for(i=0;i<n;i++){
         re.append(s.charAt(i));
      }
      return re.toString();
   }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    代码的运行结果如下所示：
    运行结果

    如果使用string的切换函数substring()，则能直观写出切片法，代码如下：

    class Solution {
   public String reverseLeftWords(String s, int n) {
      return s.substring(n,s.length())+s.substring(0,n);
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5

    代码的运行结果如下所示
    运行结果

    当然，如果StringBuiler不能使用的话，只能通过字符串add或者+操作来实现字符串的拼接，但是在java代码中，字符串的拼接实际上还是会在幕后使用到StringBuilder或者StringBuffer类型，因此频繁进行String类型的字符串拼接将会导致效率低下，实际的代码思路和“使用StringBuilder 的切片法”类似。

    5. 剑指Offer 59-I.滑动窗口的最大值

    5.1 题目

      给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

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

  提示：
  你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    5.2 解题思路

    个人的解题思路还是“暴力解法”，考虑到最大值在不在窗口中，如果还在窗口中则只比较最大值和新加入的数，如果不在窗口中则需要整体遍历滑动窗口中的所有元素。因此时间复杂度是O(nk)，最后遇到一个很长的数组，会被卡超时。

    官方题解里面用到一个队列结构存储当前窗口的最大值元素，它的维护情况如下所示：

    • 如果左边删除的窗口值是队列的头部元素，需要删除
    • 如果右边加入的元素和队列尾部的若干元素相比更大，则将队列尾部比待加入元素小的元素删除，然后把待加入元素加进去

    这样维护的队列，每次都能保证最大元素在队列的头部，只需要O（1）的时间复杂度就能够找到。

    5.3 数据类型功能函数总结

    //数组相关操作
int[] array_Name = new int[length];//数组定义
array.length;//获得数组长度
array[index];//获得数组的某个元素值
//LinkedList的相关操作
LinkedList<> LL_Name = new LinkedList<>();//LinkedList定义
LinkedList.add/get/remove + First/Last();//添加/获取/删除 头部/尾部 的元素 
LinkedList.isEmpty();//判断LinkedList是不是为空 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    5.4 java代码

    class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
      if(nums.length==0){
         return nums;
      }
      else{//数组不为0
         int[] re=new int[nums.length-k+1];
         LinkedList<Integer> deque = new LinkedList<Integer>();
         for(int i=0;i<k;i++){
            while(deque.isEmpty()==false && deque.getLast() < nums[i]){
               deque.removeLast();
            }
            deque.addLast(nums[i]);
         }
         re[0]=deque.getFirst();
         for(int i=k;i<nums.length;i++){
            if(deque.getFirst()==nums[i-k]){
               deque.removeFirst();
            }
            while(deque.isEmpty()==false && deque.getLast() < nums[i]){
               deque.removeLast();
            }
            deque.addLast(nums[i]);
            re[i-k+1]=deque.getFirst();
         }
         return re;
      }
   }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    1. java代码

    5.5 不甘心，把自己千辛万苦写的代码小贴一下（≧皿≦）（超时勿用）

    class Solution {
 public int[] maxSlidingWindow(int[] nums, int k) {
     //最简单的思路：每次k个数据逐个比较得出，但是上一个滑动窗口的最值对下一次比较有影响。
     //上一轮的max在下一轮的比较中，如果max还在滑动窗口中，max和new_number比较，如果max不在滑动窗口中，max=new_number，并和其他k-1个数逐个比较。
     int n=nums.length;
     if(n==0){
         return nums;
     }
     else{
         int[] re=new int[n-k+1];

         int max_index=0;
         for(int i=0;i<k;i++){
             if(nums[max_index] < nums[i]){
                 max_index=i;
             }
         }
         re[0]=nums[max_index];
         int count=1;
         int re_index=1;
         for(int i=1;i<=n-k;i++,re_index++){//i指向起点位置
             if(nums[max_index] < nums[i+k-1]){
                 max_index=i+k-1;
             }
             else{
                 if(count==1){//第一次比较或者max离开滑动窗口
                     max_index=i;
                     for(int j=i+1;j<i+k;j++){//遍历滑动窗口中的所有元素
                         if(nums[max_index] < nums[j]){
                             max_index = j;
                         }
                     }
                 }
             }
             if(max_index==i){//说明下一轮max离开滑动窗口
                 count=1;
             }
             else{//说明下一轮max不离开滑动窗口
                 count=0;
             }
             re[re_index]=nums[max_index];    
         }
         return re;
     }
 }        
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
  • 相关阅读:
    java-php-python-ssm郑工社团交流服务信息平台计算机毕业设计
    AQS之基础分析 (一)
    Linux学习：基本命令
    【解决方案】浅谈基于边缘计算的智慧工地解决方案
    Open AI ChatGPT Prompt 学习之基础篇
    后Kubernetes时代的虚拟机管理技术之Virtual-Kubelet篇
    linux命令查看谁在使用服务器的GPU
    计算机毕业设计之java+springboot基于vue的逍遥大药房管理系统
    【学习笔记】CF1651F Tower Defense
    conda环境下XZ_5.1.2alpha not found解决方案
  • 原文地址：https://blog.csdn.net/weixin_44201830/article/details/127601026