leetcode面试题之栈与队列

232. 用栈实现队列

题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

链接：https://leetcode.cn/problems/implement-queue-using-stacks/

思路：

用两个栈模拟队列
s1出队栈、s2入队栈

class MyQueue {
    Stack<Integer> s1, s2;
    public MyQueue() {
        s1 = new Stack<>(); // 模拟出队栈
        s2 = new Stack<>(); // 模拟入队栈
    }
    public void push(int x) {
        s2.push(x);
    }
    // 出栈时，如果s1为空，s2不为空，将s2中的数全部放入s1，再出栈；s1不为空则直接出栈
    public int pop() {
        if (s1.isEmpty()) {
            while (!s2.isEmpty()) {
                s1.push(s2.pop());
            }
        }
        return s1.pop();
    }
    // 如果s1为空，s2不为空，则把s2中的数全部放入s1，再获取栈顶元素
    public int peek() {
        if (s1.isEmpty()) {
            while (!s2.isEmpty()) {
                s1.push(s2.pop());
            }
        }
        return s1.peek();
    }
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}
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

225. 用队列实现栈

题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

链接：https://leetcode.cn/problems/implement-stack-using-queues/

思路：用一个队列模拟栈，每次出栈or取栈顶元素时，将队中元素全部出队再入队，以不同的方式处理尾元素

class MyStack {
    // 用一个队列模拟栈
    Queue<Integer> q;
    public MyStack() {
        q = new LinkedList<>();
    }
    public void push(int x) {
        q.add(x);
    }
    // 出队列，并把 除最后一个元素外 的其他元素重新放入队列
    public int pop() {
        int size = q.size();
        size --;
        while (size-- > 0) {
            q.offer(q.poll());
        }
        return q.poll();
    }
    // 出队列，把所有元素重新放入队列，当最后一个元素时，记录一下作为返回值
    public int top() {
        int size = q.size();
        while (size-- > 1) {
            q.offer(q.poll());
        }
        int res = q.poll();
        q.offer(res);
        return res;
    }
    public boolean empty() {
        return q.isEmpty();
    }
}
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

20. 有效的括号

题目：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

链接：https://leetcode.cn/problems/valid-parentheses/

思路：栈
遇到左括号入栈，右括号出栈比对，最后栈为空即为匹配成功

public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        int n = s.length();
        for (int i = 0; i < n; i ++) {
            char c = s.charAt(i);
            if (c == '(') {
                st.push(')');
            } else if (c == '{') {
                st.push('}');
            } else if (c == '[') {
                st.push(']');
            } else if (st.isEmpty() || c != st.peek()){
                return false;
            } else {
                st.pop();
            }
        }
        return st.isEmpty();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1047. 删除字符串中的所有相邻重复项

题目：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

思路：

用数组模拟栈，不用真正的栈！！
用一个下标模拟栈的栈顶指针
入栈情况：1)栈为空 2)栈不为空时，栈顶元素与遍历的字符不相等；否则出栈

public String removeDuplicates(String s) {
        // 直接用字符串模拟栈，不用真正的栈
        int top = -1; // 栈顶指针
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i ++) {
            // 入栈情况：1)栈为空 2)栈不为空时，栈顶元素与遍历的字符不相等；否则出栈
            if (top < 0 || ch[i] != ch[top]) {
                ch[++ top] = ch[i];
            } else {
                top --;
            }
        }
        return String.valueOf(ch, 0, top + 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

150. 逆波兰表达式求值

题目：根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/

思路：逆波兰表达式：用数组模拟栈
特点：操作数的个数一定比运算符的个数多 1 个，即包含最多(n+1)/2个操作数，(n-1)/2个操作符

public int evalRPN(String[] tokens) {
        // 数组模拟栈
        int top = -1, n = tokens.length;
        // 注意：操作数个数比操作运算符至少多一个，即最多包含(n+1)/2个操作数
        int[] st = new int[(n+1)/2]; 
        for (String i : tokens) {
            if ("+".equals(i) || "-".equals(i) || "*".equals(i) || "/".equals(i)) {
                int num1 = st[top --], num2 = st[top --];
                if ("+".equals(i)) st[++ top] =  num2 + num1;
                if ("-".equals(i)) st[++ top] =  num2 - num1;
                if ("*".equals(i)) st[++ top] =  num2 * num1;
                if ("/".equals(i)) st[++ top] =  num2 / num1;
            } else {
                st[++ top] = Integer.valueOf(i); // 字符串转为整型之后在入栈
            }
        }
        return st[top];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

239. 滑动窗口最大值

题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

链接：https://leetcode.cn/problems/sliding-window-maximum/

思路：单调双端队列
（一般用到单调队列思想都是双端队列）

public int[] maxSlidingWindow(int[] nums, int k) {
        // 思路：单调双端队列
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>(); // 双端队列（存放的是下标）
        for (int i = 0, idx = 0; i < n; i ++) {
            // 新来一个数，移除一个旧数
            if (!q.isEmpty() && i - k + 1 > q.peekFirst()) q.removeFirst();
            // 新来的数>队尾的数，删除队尾的数，直到新来的数<=队尾的树
            while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) q.removeLast();
            // 当前数下标入队
            q.addLast(i);
            // 每遍历一次，队头的下标就是最大值的下标
            // i从k-1的位置开始才输出队列最大值
            if (i >= k - 1) res[idx ++] = nums[q.peekFirst()];
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

347. 前 K 个高频元素

题目：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

链接：https://leetcode.cn/problems/top-k-frequent-elements/

思路：

1. map统计频次
2. 计数排序法
   （1）统计出现i次的有几个整数
   （2）找分界点，从后往前遍历n–，次数i求和直到k
   （3）遍历哈希表，次数超过n的记录答案

public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 使用map，统计每个整数出现的次数
        for (int i : nums) {
            // if (map.containsKey(i)) {
            //     map.put(i, map.get(i)+1)
            // } else {
            //     map.put(i, 1);
            // }
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        // 计数排序算法
        int n = nums.length;
        int[] cnt = new int[n + 1];
        for (int i : map.values()) {
            cnt[i] ++; // 出现i次的元素有cnt[i]个
        }
        // 找分界点，从后往前遍历，直到下标凑到k
        int m = 0;
        while (m != k) {
            m += cnt[n --];
        }
        int[] res = new int[k];
        m = 0;
        // 遍历哈希表，如果次数超过n，记录答案
        for(int i: map.keySet()){
            if(map.get(i) > n){
                res[m ++] = i;
            }
        }
        return res;
    }
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