刷Leecode笔记（四）栈与队列篇

栈与队列篇

用队列实现栈，有效的括号，逆波兰表达式，滑动窗口最大值，前K个高频元素

栈与队列

232.用栈实现队列

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    public MyQueue() {
        stackIn = new Stack<>();// 负责进栈
        stackOut = new Stack<>();// 负责出栈
    }
    // 入队的操作,过程即将数据压入进栈
    public void push(int x) {
        stackIn.push(x);
    }
    public void InTuOut() {
        if (!stackOut.isEmpty()) {
            return;
        }
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
    // 从队列的开头移除元素，将In栈的元素全部放到out栈中，
    // 再从out栈移除即可，所以需要写一个移动函数
    public int pop() {
        InTuOut();
        return stackOut.pop();
    }
    public int peek() {
        InTuOut();
        return stackOut.peek();
    }
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}
//模拟，理清思路路，用两个栈模拟队列，入栈的时候，入栈IN，出栈的时候，将In栈内元素全部转到OUT栈，再出栈，

225.用队列实现栈

//用两个队列，实现。这样实现没什么意思不想写了

20.有效的括号

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else {
                if (stack.isEmpty() || c != stack.pop()) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
//匹配括号，检测到左括号，就入栈右括号即可，最后栈空，或者栈顶元素不等于匹配的元素，就返回false

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

class Solution {
    public String removeDuplicates(String s) {
        int n = s.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (stack.isEmpty() || c != stack.peek()) {
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        // StringBuilder sb = new StringBuilder();
        // while (!stack.isEmpty()) {
        // sb.append(stack.pop());
        // }
        // sb.reverse();
        // return sb.toString();
        String str = "";
        while (!stack.isEmpty()) {
            str = stack.pop() + str;
        }
        return str;
    }
}
//使用栈，栈空或者下一个字符与栈不同，则入栈，反之出栈，
//使用StringBuilder循环接受出栈元素
//或者直接拼接，为什么直接拼接190ms比循环遍历反转80ms慢了这么多？搞不懂了

150.逆波兰表达式

//思路很简单，遇到数字压入栈，遇到字符出栈，计算结果并且入栈，
/*实现过程中的问题，可是给的是String类型的数组，不能用==判断，==判断的是地址值是否相等，charAt()转为字符类型后，因为后面运算要使用Intege.valueOf()把String转为int类型的，所以直接用Sting类型的，调用equals方法去比较值的相等即可
*/
class Solution {
    public int evalRPN(String[] tokens) {
        int n = tokens.length;
        Stack<Integer> sk = new Stack<>();
        for (int i = 0; i < n; i++) {
            String s = tokens[i];
            switch (s) {
                case "+":
                    sk.push(sk.pop() + sk.pop());
                    break;
                case "-":
                    sk.push(-sk.pop() + sk.pop());
                    break;
                case "*":
                    sk.push(sk.pop() * sk.pop());
                    break;
                case "/":
                    // sk.push(sk.pop() / sk.pop());
                    int first = sk.pop();
                    int end = sk.pop();
                    sk.push(end / first);
                    break;
                default:
                    sk.push(Integer.valueOf(s));
                    break;
            }
        }
        return sk.pop();
    }
}
//注意乘法和加法无所谓，没有顺序，除法和减法有顺序的，要注意先后顺序

239.滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i <= n - k; i++) {
            int left = i;
            int right = i + k - 1;
            int max = nums[left];
            for (int j = left + 1; j <= right; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                }
            }
            list.add(max);
        }
        int[] ans = new int[list.size()];
        int count = 0;
        for (int i : list) {
            ans[count++] = i;
        }
        return ans;
    }
}
//暴力法，在滑动的数组中寻找最大值，再赋值给数组，复杂度O(n^2)，暴力超时
//可以考虑使用一个双端队列，记录首个范围的最大值max，入队操作，若right大，则左边的全部出队，若已有的大，入队就行（长度大于k左边出队），模拟是这个模拟，代码谢不出来

347.前k个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        // map记录元素以及元素出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 将map中所有key-value的集合转换为list集合
        // Map.Entry表示java中操作键值对的接口，Map 接口的实现类（如 HashMap）的 entrySet() 方法返回一个包含 Map.Entry
        // 对象的集合
        List<Map.Entry<Integer, Integer>> list = new ArrayList(map.entrySet());
        // 重写comparator方法。通过比较value的值进行排序
        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        // 排序后输出前k个高频元素的key值
        for (int i = 0; i < k; i++) {
            ans[i] = list.get(i).getKey();
        }
        return ans;
    }
}
/*能想到的常规思路只有，使用HashMap计数，再通过value的值排序，得到前k个高频次的元素，在对map中的value值排序中遇到的问题已经写在了注释里

其他题解：使用优先队列，使用堆，我都看不懂
*/