3.7 特殊数据结构:单调栈

3.7.1 单调栈解题模板

• 单调栈:可以使得每次新元素入栈后，栈内的元素都保持单调(单调递增或者单调递减)

• 单调栈一般用来决绝Next Greater Element

• nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置右侧的第一个比 x大的元素。

  给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

  对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

  返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

  来源：力扣（LeetCode）
  链接：https://leetcode.cn/problems/next-greater-element-i
  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 比如说输入一个数组nums= [2,1,2,4,3]，算法将返回[4,2,4,-1,-1]

  • 解释:首先第一个元素2,然后就去后面找，发现比2大的数是4，于是新数组的第一个元素就是4
  • 第二个元素是1，然后去后面找，发现比1大的数是2，于是新数组的第二个元素就是2
  • …第四个元素是4，然后去后面找，发现没有比4大的数，于是新数组的第四个元素就是-1

• 暴力的解法时间复杂度是O(n^2),n的最大值是1000，也就是最差情况下将有1000*1000次计算,1e6

• 这个问题可以这样抽象思考:把数组元素想象成并列站立的人，元素大小想象成人的身高，这些人面对你站成一列，如何求元素"2"的nextGreaterNumber呢?很简单，如果能够看到元素"2"，那么他后面可见的第一个人就是"2"的NextGreaterNumber，因为比2小的元素身高不够，都被2挡住了，第一个露出来的就是答案

• 单调栈解决问题的模板

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];//存放答案的数组
        Stack<Integer> s = new Stack<>();
        for(int i = nums2.length-1;i>=0;i--) {//倒着往栈里面放
            while (!s.empty() && s.peek() <= nums2[i]) {//判断个子高矮
                s.pop();//矮个子出列
            }
            ans[i] = s.empty() ? -1 : s.peek();//这个元素身后的第一个搞个
            s.push(nums2[i]);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12

• for循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈
• while循环是把两个高个元素之间的元素给排除掉，因为他们的存在是没有意义的，前面挡着个子更高的元素，因此它们不可能被作为后续进来的元素的NextGreaterNumber了
• 这个算法的时间复杂度并不直观，从整体来看总共有n个元素，当每个元素都被push入栈了一次，而最多会被pop一次，没有任何冗余的操作，所以总的计算规模是和元素规模n成正比的，也就是O(n)的复杂度

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        Stack<Integer> s = new Stack<>();
        Map m = new HashMap<Integer,Integer>();//可以存储下标,依然可以得到答案
        //倒着遍历,倒着入栈,正着出栈
        for(int i = nums2.length-1;i>=0;i--){
            //排除掉栈中小于nums2[i]的元素,因为压根都看不到了
            while(!s.isEmpty() && s.peek() <= nums2[i]){
                s.pop();
            }
            m.put(nums2[i],s.isEmpty()? -1:s.peek());
            s.push(nums2[i]);
        }
        for(int i= 0;i<nums1.length;i++){
            ans[i] = (int)m.get(nums1[i]);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.7.2 题目变形

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/iIQa4I
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 给你一个数组T，这个数组存放的是最近几天的气温，算法需要返回一个数组，请计算对于每一条，还要至少等多少太难才能等到一个更暖和的气温，如果等不到那一天，填0

    public  int[] dailyTemperatures(int[] temperatures) {
        int[] ans = new int[temperatures.length];
        Stack<Integer> s = new Stack<>();//这里应当存放的是数组的下标
        for(int i = temperatures.length-1;i>=0;i--){
            while(!s.isEmpty() && temperatures[i]>= temperatures[s.peek()]){
                s.pop();
            }
            ans[i] = s.isEmpty()?0:(s.peek()-i);
            s.push(i);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12

3.7.3 如何处理环形数组

• 现在假设给你的数组是一个环形数组，该如何处理呢?
• 给你一个数组[2,1,2,4,3]，返回数组[4,2,4,-1,4]，拥有了环形属性，最后一个元素3绕了一圈后找到了比自己大的元素4
• 计算机的内存都是线性的，没有真正意义上的环形数组，但是我们可以模拟出环形数组的效果，一般都是通过%来实现的
• 当增加了环形这个限制后，问题的难点就转移到了这个Next的意义不仅是当前元素的右边了，有可能了转了一圈出现在当前元素的左边，可以考虑这样一个思路:将原始数组翻倍，就是在后面再接一个原始数组，这样的话，按照之前比身高的流程，每个元素不仅可以比较自己右边的元素，而且还就可以和左边的元素比较了
• 技巧:除了最直观地复制一份数组接到原数组后面之外，我们还可以通过指针取余+扩大遍历范围的方式来模拟

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Stack<Integer> s = new Stack<>();
        for(int i =2*n-1;i>=0;i--){
            while(!s.isEmpty() && s.peek() <= nums[i]){
                s.pop();
            }
            ans[i%n] = s.isEmpty()?-1:s.peek();
            s.push(nums[i%n]);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

3.8 特殊数据结构:单调队列

• 单调队列:可以使得队列中的元素全都是单调递增(或者递减的)

• 该数据结构可以结局滑动窗口的一系列问题:

• 输入一个数组nums和一个正整数k,有一个大小为k的窗口在nums上从左到右滑动，请输出每次滑动时窗口中的最大值

• 这道题的暴力解法还是比较容易的，但是这道题要考察的是如何在O(1)的限制下算出每个窗口中的最大值，使得整个算法在线性时间内完成，这种问题的一个特殊点在于，窗口是不断滑动的，也就是需要动态地计算窗口中的最大值

• 在一堆数字中，已经知道最值为A，如果给这堆数添加一个数B，那么比较一下A和B就可以立即算出新的最值，但是如果减少一个数，就不能够直接得到最值了，因为如果减少的这个数恰好就是数A，就需要遍历所有数重新找出新的最值

• 在这道题的场景中，每个窗口前进的时候，需要同时添加一个数减少一个数，所以想要在O(1)的时间内得出新的最值，需要依靠单调队列这种数据结构来辅助

    class MonotonicQueue{
        void push(int n){//在队尾添加元素n

        }
        int max(){
            //返回当前队列的最大值
            return 0;
        }
        void pop(int n){//队头元素如果是n,那么删除它
            
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        MonotonicQueue window = new MonotonicQueue();
        for(int i = 0;i<nums.length;i++){
            //先把窗口的k-1给填满
            if(i<k-1){
                window.push(nums[i]);
            }else{//开始滑动窗口
                //窗口向前滑动
                //移入新元素
                window.push(nums[i]);
                //将当前窗口中的最大元素计入结果
                list.add(window.max());
                //移出最后到的元素
                window.pop(nums[i-(k-1)]);
            }
        }
        int[] arr = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
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

• 观察滑动窗口的过程容易知道，实现单调队列必须使用一种数据结构支持在头部和尾部进行插入和删除，很显然双链表是符合这个条件的
• 单调队列的核心思路和单调栈类似,push方法依然是在队尾添加元素，但是要把前面比自己小的元素都给删除掉

    class MonotonicQueue{
        private LinkedList<Integer> q = new LinkedList<>();
        public void push(int n){//在队尾添加元素n
            while(!q.isEmpty() && q.getLast()<n){//在添加的时候，要把前面小于自己的元素都给删除掉
                q.pollLast();
            }
            q.addLast(n);
        }
        int max(){//由于插入逻辑的设计,在队头的肯定是最大的,后来者如果更大,会把之前的都给压扁掉
            return q.getFirst();
        }
        void pop(int n){//队头元素如果是n,那么删除它
            if(n == q.getFirst()){
                //为什么要多此一举呢?删除不就删除嘛?这是因为在删除的时候
                //我们无法确定在插入的时候,那个后来者是否把在它之前的这个数给删掉了,假如说删掉了,那么就不用删了
                q.pollFirst();
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 算法时间复杂度分析

• 算法的整体时间复杂度依然是O(N)线性的，nums中的每个元素最多被pollLast和addLast一次，没有任何多余的操作。

• 不要搞混单调队列和优先级队列，单调队列在添加元素的时候靠删除元素保持队列的单调性，相当于抽取出某个函数中单调递增(递减)的部分，而优先级队列(二叉堆)相等于会自动排序

3.9 判断回文链表

3.9.1 判断回文单链表

• 给你一个单链表的头节点，请你判断这个链表中的数字是不是回文

• 这道题的关键在于，单链表无法倒着遍历，无法使用双指针的技巧，那么最简单的办法就是我新开一个链表，然后把这个链表给翻转，然后两边同时遍历，看一不一样

• 其实，借助二叉树的后续遍历的思路，不需要显示地翻转链表也可以倒序遍历链表，或者借助栈等结构也可以,只是需要两次遍历

• 链表兼具有递归结构，树结构不过是链表的衍生，因此链表也有前序遍历和后序遍历，但是没有中序遍历。

void traverse(ListNode head){
    //前序遍历代码
    traverse(head.next);
    //后序遍历代码
}
1
2
3
4
5

• 如果想要正序打印链表中的val值，可以在前序遍历位置写代码
• 如果想要逆序打印链表中的val值，可以在后续遍历位置写代码

void traverse(ListNode head){
    //前序遍历代码
    if(head == null) return;
    traverse(head.next);
    //后序遍历代码
}
1
2
3
4
5
6

    //模仿双指针写法
    ListNode left;//左侧指针
    public boolean isPalindrome(ListNode head) {
        left = head;
        return traverse(head);
    }
    private boolean traverse(ListNode right){
        if(right == null){
            return true;
        }
        boolean res = traverse(right.next);
        //后序遍历代码
        res = res && (right.val == left.val);
        left = left.next;
        return res;
    }

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

• 实际上就是把链表节点放入一个栈，然后再拿出来，这时候的元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已，时间空间复杂度依然是O(N)

3.9.2 优化空间复杂度

[优化1] 通过双指针技巧中的快慢指针来找到链表的中点

ListNode slow,fast;
slow = fast = head;
while(fast !=null && fast.next!=null){
    slow = slow.next;
    fast = fast.next.next;
}
//slow指针现在指向链表的中点
1
2
3
4
5
6
7

• 这里要分情况，如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步

if(fast != null){
    slow = slow.next;
}
1
2
3

• 从slow开始反转后面的链表，现在就可以开始比较回文串了

ListNode left = head;
ListNode right =reverse(slow);
while(right !=null){
    if(left.val != right.val){
        return false;
    }
    left = left.next;
    right = right.next;
    return true;
}
1
2
3
4
5
6
7
8
9
10

    public boolean isPalindrome(ListNode head) {
        //1.先找到链表的中点
        ListNode slow=head,fast = head;
        while(fast !=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast!=null){
            slow = slow.next;
        }
        ListNode left = head;
        ListNode right = reverse(slow);
        while(right!=null){
            if(left.val != right.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    //翻转以head为头的链表,返回翻转之后的头节点
    ListNode reverse(ListNode head){
        ListNode pre = null,cur= head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
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

3.10 纯递归反转链表

• 给你一个索引区间，让你把单链表中的这部分元素反转，其他部分不变
• 如果使用迭代的方式，思路大概是先用一个for循环定位到第m个位置，然后用传统的方法将m到n这一段的元素之间反转即可

下面我们采用纯递归的方式来反转一个链表

    ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
1
2
3
4
5
6
7
8
9

• 对于递归算法，最重要的是明确定义递归函数的行为:输入一个节点head,将以head为起点的链表反转，并返回反转完成后的链表头节点
• 递归函数要有basecase的，也就是当链表只有一个节点，或者链表没有节点的时候，反转也是它自己，直接返回即可
• 当链表递归反转之后，新的头节点是last,而之前的head变成了置换一个节点，别忘了之后链表的末尾要指向null

3.10.1 反转链表的前N个节点

    ListNode successor =null;//后驱节点
    ListNode reverseN(ListNode head,int n){
        if(n==1){
            //记录第n+1个节点,后面要用,
            successor = head.next;
            return head;
        }
        //以head.next为起点,需要翻转前n-1个节点
        ListNode last = reverseN(head.next,n-1);
        head.next.next = head;
        //让反转之后的head节点和后面的节点连起来
        head.next=successor;
        return last;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

反转前N个节点和反转整个链表的区别

• basecase变为n==1,反转一个元素，就是它本身
• 要记录后驱节点successor
• 反转整个链表时，直接把head.next设置为null，因为整个链表反转后原来的head变成了整个链表的最后一个节点，但现在head节点在递归翻转之后不一定是最后一个节点，因此我们要记录后驱节点successor(第n+1个节点)，翻转之后把它给连接上就好了

3.10.2 翻转链表的一部分

• 现在给一个索引区间[m,n]m从1开始，仅仅翻转区间中的链表元素，首先，如果m==1，就相当于翻转链表开头的n个元素，也就是刚才实现的功能

• 如果m!=-1时，我们把head的索引看作为1，那么我们是想从第m个元素开始反转，如果把head.next的索引视为1，那么相对于head.next,那么反转的区间是从第m-1个元素开始的，那么相对于head.next.next呢？

• 和迭代思想不同，这就是递归思想

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //base-case
        if(left == 1){
            //相当于翻转前n个元素
           return reverseN(head,right);
        }
        //对于head.next来说,就是反转区间[m-1,n-1]
        //前进到翻转的起点触发base-case
        head.next = reverseBetween(head.next,left-1,right-1);
        return head;
    }

    ListNode successor =null;//后驱节点
    ListNode reverseN(ListNode head,int n){
        if(n==1){
            //记录第n+1个节点,后面要用,
            successor = head.next;
            return head;
        }
        //以head.next为起点,需要翻转前n-1个节点
        ListNode last = reverseN(head.next,n-1);
        head.next.next = head;
        //让反转之后的head节点和后面的节点连起来
        head.next=successor;
        return last;
    }
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

3.11 k个一组反转链表

3.11.1 分析问题

• 输入一个单链表和一个正整数k，请以每k个节点为一组反转这条链表，然后返回反转之后的结果，如果链表长度不是k的整数倍，那么最后不足k个节点保持原有顺序
• 首先明确，这个问题具有递归性质
• 什么叫做递归性质?比如对这个链表调用reverseKGroup(head,2)，也就是以两个节点为一组反转链表，如果设法把前两个节点给反转，那么后面的那些节点如何处理？后面的这些节点也是一条链表，而且规模(长度)比原来这条链表要小，这就叫子问题
• 也就是说reverseKGroup函数只需要关心如何反转前k个节点，然后递归调用自己即可，因为子问题和原问题的结构完全相同，这就是所谓递归的性质
• [1] 先反转以head开头的k个元素
• [2] 将第k+1个元素作为head递归调用reverseKGroup函数
• [3] 将上述两个过程结果连接起来
• 最后一点值得注意的是，递归问题都有base-case,对于这个问题而言，base-case就是当最后的元素不足k个时候，就保持不变，这就是base-case

3.11.2 代码实现

• 首先来回顾一下正常的翻转链表的代码

    public ListNode reverse(ListNode head){
        ListNode pre=null,cur=head,next=null;
        while(cur!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur=next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10

• 这其实就是反转节点a到null之间的节点，如果要反转a到b之间的节点，只需要将null修改成b即可

    public ListNode reverse(ListNode a,ListNode b){
        ListNode pre=null,cur=a,next=a;
        while(cur!=b){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur=next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10

    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null){
            return null;
        }
        ListNode a,b;
        a=b=head;
        for(int i =0;i<k;i++){
            //不足k个,不需要反转,base-case
            if(b==null){
                return head;
            }
            b=b.next;
        }
        //反转前k个元素
        ListNode newHead = reverse(a,b);
        a.next = reverseKGroup(b,k);
        return newHead;
    }

    public ListNode reverse(ListNode a,ListNode b){
        ListNode pre=null,cur=a,next=a;
        while(cur!=b){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur=next;
        }
        return pre;
    }
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