代码随想录之栈与队列篇T232-使用栈实现队列

见力扣第232题[使用栈实现队列]

题目描述

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

实现 MyQueue 类：

我的思路

class MyQueue {
    private Stack pushStack;
    private Stack popStack;
    
    
    public MyQueue() {
        this.pushStack = new Stack<>();
        this.popStack = new Stack<>();
    }
    public void push(int x) {
        pushStack.push(x);
    }
    public int pop() {
        // 先检查 popStack 中是否有元素
        if (popStack.isEmpty()) {
            transfer(pushStack, popStack);
        }
        // 从 popStack 中弹出元素
        return popStack.pop();
    }
    public int peek() {
        if (popStack.isEmpty()) {
            transfer(pushStack, popStack);
        }
        return popStack.peek();
    }
    public boolean empty() {
        return popStack.isEmpty() && pushStack.isEmpty();
    }
    
    private void transfer(Stack pushStack, Stack popStack) {
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
    }
}

T225-使用队列实现栈

见力扣第225题[使用队列实现栈]

题目描述

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

实现 MyStack 类：

我的思路

class MyStack {
    private final ArrayList list;
    private int sz;
    public MyStack() {
        list = new ArrayList<>();
        sz = 0;
    }
    public void push(int x) {
        list.add(x);
        sz++;
    }
    public int pop() {
        int val = list.get(sz - 1);
        list.remove(sz - 1);
        sz--;
        return val;
    }
    public int top() {
        return list.get(sz - 1);
    }
    public boolean empty() {
        return sz == 0;
    }
}

T20-有效的括号

见力扣第20题[有效的括号]

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

我的思路

判断stack是否为空

public boolean isValid(String s) {
    if (s.length() % 2 != 0) return false;
    Stack stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && (c - stack.peek()) <= 2 && (c - stack.peek()) > 0) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

T1047-删除字符串中的所有相邻重复项

见力扣第1047题[删除字符串中的所有相邻重复项]

题目描述

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

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

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

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

我的思路

public String removeDuplicates(String s) {
    if (s.length() <= 1) return s;
    ArrayDeque q = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (!q.isEmpty() && c == q.peekLast()) {
            q.removeLast();
        } else {
            q.addLast(c);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (char c : q) {
        sb.append(c);
    }
    return sb.toString();
}

T150-逆波兰表达式求值

见力扣第150题[逆波兰表达式求值]

题目描述

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

我的思路

返回操作数栈中的运算结果

public int evalRPN(String[] tokens) {
    if (tokens.length <= 2) return Integer.parseInt(tokens[tokens.length - 1]);
    int[] dataStack = new int[tokens.length / 2 + 1]; // 最多 n / 2 + 1 个操作数
    int index = 0; // 模拟栈帧
    for (String token : tokens) {
        switch (token) {
            case "+": {
                // 加法，取出两位操作数相加，计算结果赋值到第一个操作数的位置
                dataStack[index - 2] = dataStack[index - 2] + dataStack[index - 1];
                // 栈帧指向有效操作数的后一位
                index--;
                break;
            }
            case "-": {
                dataStack[index - 2] = dataStack[index - 2] - dataStack[index - 1];
                index--;
                break;
            }
            case "*": {
                dataStack[index - 2] = dataStack[index - 2] * dataStack[index - 1];
                index--;
                break;
            }
            case "/": {
                dataStack[index - 2] = dataStack[index - 2] / dataStack[index - 1];
                index--;
                break;
            }
            default: {
                // 操作数，直接入栈
                dataStack[index++] = Integer.parseInt(token);
            }
        }
    }
    return dataStack[0];
}

时间复杂度：O(N)O(N)O(N)，需要遍历一次tokens数组

空间复杂度：O(N)O(N)O(N)，需要长度为(n/2)+1(n / 2) + 1(n/2)+1的数组模拟栈

T239-滑动窗口最大值

见力扣第239题[滑动窗口最大值]

题目描述

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

返回 滑动窗口中的最大值 。

示例 1：

输入：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

我的思路

超时

思路

public int[] maxSlidingWindowI(int[] nums, int k) {
    int n = nums.length;
    Deque dq = new ArrayDeque<>();
    int[] res = new int[n - k + 1];
    int l = 0;
    int r = 0;
    while (r < k) {
        while (!dq.isEmpty() && nums[r] >= nums[dq.peekLast()]) {
            dq.pollLast();
        }
        dq.offerLast(r++);
    }
    res[l] = nums[dq.peekFirst()];
    while (r < n) {
        // 如果队尾索引指向的元素小于或者等于准备的入队的元素，直接弹出
        while (!dq.isEmpty() && nums[r] >= nums[dq.peekLast()]) {
            dq.pollLast();
        }
        dq.offerLast(r++);
        l++;
        // 如果队首索引不在窗口中
        while (dq.peekFirst() < l) {
            dq.pollFirst();
        }
        res[l] = nums[dq.peekFirst()];
    }
    return res;
}

T347-前K个高频元素

见力扣第347题[前K个高频元素]

题目描述

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

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

我的思路

public int[] topKFrequent(int[] nums, int k) {
    Map map = new HashMap<>();
    for (int num : nums) {
        if (!map.containsKey(num)) {
            map.put(num, 0);
        }
        map.put(num, map.get(num) + 1);
    }
    List<int[]> frequency = new ArrayList<>();
    for (Map.Entry entry : map.entrySet()) {
        int[] pairs = new int[2];
        pairs[0] = entry.getKey();
        pairs[1] = entry.getValue();
        frequency.add(pairs);
    }
    Collections.sort(frequency, (o1, o2) -> o2[1] - o1[1]);
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = frequency.get(i)[0];
    }
    return res;
}

优化方案

public int[] topKFrequentI(int[] nums, int k) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    int[] ans = new int[k];
    // 找到数组中的最大值和最小值
    for (int i : nums) {
        max = Math.max(i, max); // 更新最大值
        min = Math.min(i, min); // 更新最小值
    }
    // 创建一个桶数组，用于记录每个数字出现的频率
    int[] buckets = new int[max - min + 1];
    for (int num : nums) {
        buckets[num - min]++; // 将数字映射到桶数组中，并增加频率
    }
    // 找到桶数组中的最大频率
    int maxF = 0;
    for (int bucket : buckets) {
        maxF = Math.max(bucket, maxF); // 更新最大频率
    }
    int index = 0; // 结果数组的索引
    // 找到出现频率最高的 k 个数字
    while (index < k) {
        for (int i = 0; i < buckets.length; i++) {
            if (maxF == buckets[i]) {
                ans[index] = i + min; // 将数字从桶数组映射回原数组的值
                index++;              // 更新结果数组的索引
            }
        }
        maxF--; // 减少最大频率，继续查找下一个频率最高的数字
    }
    return ans; // 返回结果数组
}

总结