31.栈的压入、弹出序列

题目
牛客网
思路
方法：栈
用一个栈来模拟两个序列是否符合入栈出栈的次序，对于入栈序列，只要栈为空，序列肯定要依次入栈，当遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。

注：重点弄清楚入栈时要满足的条件。

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
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    
    		// 创建辅助栈
        Stack<Integer> s = new Stack<>();
        
        int n = pushA.length;
        
        // 初始化入栈的下标
        int j = 0;
        
        // 遍历出栈的数组
        for (int i = 0;i < n;i++) {
            
            // 入栈：栈为空或者栈顶不等于出栈数组
            while ((j < n) && (s.isEmpty() || (s.peek() != popA[i]))) {
                s.push(pushA[j]);
                j++;
            }
            
            // 栈顶等于出栈数组
            if (s.peek() == popA[i]) {
                s.pop();
            }
            // 不匹配序列
            else {
                return false;
            }
        }
        
        return true;
    }
}

40.最小的k个数

题目
牛客网
思路
方法：堆排序
要找到最小的k个元素，只需要准备k个数字，之后每次遇到一个数字能够快速的与这k个数字中最大的值比较，每次将最大的值替换掉，那么最后剩余的就是k个最小的数字了。使用优先队列（大根堆），只要限制堆的大小为k，那么堆顶就是k个数字的中最大值，如果需要替换，将这个最大值拿出，加入新的元素就好了。
由于PriorityQueue默认是小根堆，所以要重写比较器来实现大根堆。

1
2
// 构建一个大顶堆
PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> (o2 - o1));
1
2
3
4
5
// 较小元素入堆
if (q.peek() > input[i]) {
    q.poll();
    q.offer(input[i]);
}

注：因为使用大顶堆才能控制住堆内的元素都是<=顶值的，这样就能找到最小的k个值。

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
import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        
        // 排除特殊情况
        if ((k == 0) || (input.length == 0)) {
            return res;
        }
        
        // 构建大顶堆
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> (o2 - o1));
        
        // 构建一个k个大小的堆
        for (int i = 0;i < k;i++) {
            q.offer(input[i]);
        }
        
        // 将较小的元素入堆
        for (int i = k;i < input.length;i++) {
            if (q.peek() > input[i]) {
                q.poll();
                q.offer(input[i]);
            }
        }
        
        // 堆中元素取出入数组
        for (int i = 0;i < k;i++) {
            res.add(q.poll());
        }
        
        return res;
    }
}

41.1数据流中的中位数

题目
牛客网
思路
插入排序：
每进来一个数字就用插入排序将已有的数字进行排序，然后利用计数器找到中位数。
时间复杂度：Insert函数O(n)，不管遍历还是插入都是O(n)，GetMedian函数O(1)，直接访问。
空间复杂度：O(n)，记录输入流的数组
堆排序：
创建两个堆把数字分成左右两个部分，并且保证右堆比左堆中的数字都要大，所以要左堆是大根堆，右堆是小根堆，这样就能够完成将数据分成左小右大的两部分。以为将数据变得完全有序，所以相对插入排序来说减少了部分时间开销。
时间复杂度：Insert函数O(log2n)，维护堆的复杂度，GetMedian函数O(1)，直接访问。
空间复杂度：O(n)，两个堆的空间，虽是两个，但是一个堆最多n/2
堆排序实现代码：

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
import java.util.*;

public class Solution {
    
    // 定义两个堆，左边为大堆，右边为小堆
    PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> (o2 - o1));
    PriorityQueue<Integer> right = new PriorityQueue<>();
    
    // 记录插入了多少个数字
    int n = 0;

    public void Insert(Integer num) {
        
        n++;
        
        
        if (n % 2 == 0) {  
        		/* 先将数字放入左堆，左堆根代表所有
        		插入左堆中数字的最大值，然后将左堆根
        		从左堆删除放入右堆中，这样就能保证所
        		有的右堆数字比左堆大
        		*/
            left.offer(num);
            right.offer(left.poll());
        }
        else {
            right.offer(num);
            left.offer(right.poll());
        }
        
    }

    public Double GetMedian() {
        
        // 当有偶数个数字时，返回左右堆根的平均值
        if (n % 2 == 0) {
            return ((left.peek() + right.peek()) / 2.0);
        }
        // 当有基数个数字时返回左堆根，因为从左堆开始放数字
        else {
            return (double)left.peek();
        }
    }


}

41.2字符流中第一个不重复的字符

题目
牛客网
思路
方法：哈希表+字符串
又是一个找到是否重复的问题。我们还是可以用哈希表来记录各个字符出现的次数，根据这样只要是字符串最前面且哈希表中次数为1的字符就是我们要找的。

复杂度分析：

  • 时间复杂度：O(n)，每次插入字符都是O(1)，每次查询需要遍历字符串O(n)
  • 空间复杂度：O(n)，字符一定在ASCII范围内，因此哈希表大小为常数，但是记录的字符串长度为n
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
import java.util.*;

public class Solution {

		// 初始化字符串和hashmap
    private StringBuffer s = new StringBuffer();
    private HashMap<Character, Integer> mp = new HashMap<>();
    
    public void Insert(char ch) {
        s.append(ch);
        
        // 将字符和字符对应的出现次数加入map容器
        mp.put(ch, (mp.getOrDefault(ch, 0) + 1));
    }

    public char FirstAppearingOnce() {
    
    		// 查询字符串中每个字符出现的次数并比较
        for (int i = 0;i < s.length();i++) {
            
            // 如果字符出现的次数等于1则返回这个字符
            if (mp.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
            
        }
        
        // 没有存在只出现一次的字符返回#
        return '#';
    }
}

59.滑动窗口的最大值

题目
牛客网
思路
方法：双向队列
我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，因为它们必定会比A早离开窗口，在A离开之前都争不过A，所以A在进入时依次从尾部排除掉之前的小值再进入，而每次窗口移动要弹出窗口最前面值，因此队首也需要弹出，所以我们选择双向队列。

复杂度分析：

  • 时间复杂度：O(n)，数组长度为n，只遍历一遍数组
  • 空间复杂度：O(m)，窗口长度m，双向队列最长时，将窗口填满

注：题目比较难，难点是要满足时间复杂度要求

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
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        
        // 窗口大于数组长度的时候，返回空
        if ((size <= num.length) && (size != 0)) {
            
            // 双向队列
            ArrayDeque<Integer> dq = new ArrayDeque<>();
            
            // 先遍历第一个窗口
            for (int i = 0;i < size;i++) {
                
                // 去掉比自己先进队列的小于自己的值
                while (!dq.isEmpty() && num[dq.peekLast()] < num[i]) {
                    dq.pollLast();
                }
                
              	// dq.offer(i)等同于dq.offerLast(i);
                dq.offer(i);
            }
            
            // 遍历后续数组元素
            for (int i = size;i < num.length;i++) {
                
                // 取窗口内的最大值
                res.add(num[dq.peekFirst()]);
                
              	// (i - size + 1)为窗口的下标的最小值
                while (!dq.isEmpty() && (dq.peekFirst() < (i - size + 1))) {
                		// 弹出窗口移走后的值
                    dq.pollFirst();
                }
                
                // 加入新的值前，去掉比自己先进队列的小于自己的值
                while (!dq.isEmpty() && num[dq.peekLast()] < num[i]) {
                    dq.pollLast();
                }
                
                dq.offer(i);
            }
            
            res.add(num[dq.pollFirst()]);
        }
        
        return res;
    }
}