LeetCode刷题Day11——栈和队列（逆波兰表达式、优先队列、单调队列）

/**
 * <pre>
 * 用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/12 12:04
 */
public class 逆波兰表达式求值150 {
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int a, b;
        for (String token : tokens) {
            switch (token) {
                case "+" -> {
                    a = stack.pop();
                    b = stack.pop();
                    stack.push(a + b);
                }
                case "-" -> {
                    a = stack.pop();
                    b = stack.pop();
                    stack.push(b - a);
                }
                case "*" -> {
                    a = stack.pop();
                    b = stack.pop();
                    stack.push(a * b);
                }
                case "/" -> {
                    a = stack.pop();
                    b = stack.pop();
                    stack.push(b / a);
                }
                default -> stack.push(Integer.valueOf(token));
            }
        }
        return stack.peek();
    }
}

/**
 * <pre>
 * 1.优先队列，维护元素和其下标，每次移动时将元素入队，只有队列最大元素下标在窗口外时才需移除，然后将最大值记录下来
 * 2.单调队列（当元素比你强还比你年轻时，你就可以滚了）：维护一个队列存储元素的下标，队列中的下标对应的值按从大到小排序，每次遍历一个新的元素，让他取代掉队列中比他小的元素，然后将队首元素作为当次的最大值(前提是队首元素还在窗口内，通过下表判断)
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/12 13:38
 */
public class 滑动窗口最大值239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] == o2[0] ? o2[1]-o1[1] : o2[0]-o1[0]); // 如果两个数一样大，就让序号大的排在前面（减少删除的次数）
        int[] res = new int[nums.length-k+1];
        for (int i=0; i<k; i++) {
            queue.add(new int[]{nums[i], i});
        }
        res[0] = queue.peek()[0];
        for (int i=k; i<nums.length; i++) {
            queue.add(new int[]{nums[i], i});
            while (queue.peek()[1] <= i-k) {
                queue.poll(); // 如果最大元素不在窗口内，那么就将其删除
            }
            // 到这里说明最大元素是在窗口内的，那么当前这个队列的最大元素就是窗口的最大元素
            res[i-k+1] = queue.peek()[0];
        }
        return res;
    }
    public int[] maxSlidingWindow2(int[] nums, int k) {
        Deque<Integer> integerDeque = new LinkedList<>();
        int[] res = new int[nums.length-k+1];
        for (int i=0; i<nums.length; i++) {
            while (!integerDeque.isEmpty() && nums[integerDeque.peekLast()] <= nums[i]) {
                integerDeque.pollLast();
            }
            integerDeque.add(i);
            if (integerDeque.peek() <= i - k) {
                integerDeque.poll();
            }
            if (i >= k-1) {
                res[i-k+1] = nums[integerDeque.peek()];
            }
        }
        return res;
    }
}

/**
 * <pre>
 * 1.最容易想到的是给出现次数的数组进行排序，然后需要nlogn的时间复杂度
 * 2.使用优先队列维护一个小顶堆，当堆的数量等于k时，后面元素插入时先跟堆顶元素比较，如果大于则弹出堆顶元素，将当前值插入
 * 3.基于快速排序
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/12 15:05
 */
public class 前K个高频元素347 {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.add(new int[]{num, count});
                }
            } else {
                queue.add(new int[]{num, count});
            } 
        }
        int[] res = new int[k];
        for (int i=0; i<k; i++) { // 这里需要i<k而不能需要size，因为每次poll之后size会减少
            res[i] = queue.poll()[0];
        }
        return res;
    }
    // 基于快速排序
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<int[]> values = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            values.add(new int[]{num, count});
        }
        int[] ret = new int[k];
        qsort(values, 0, values.size() - 1, ret, 0, k);
        return ret;
    }
    public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
        int picked = (int) (Math.random() * (end - start + 1)) + start;
        Collections.swap(values, picked, start);
        int pivot = values.get(start)[1];
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            if (values.get(i)[1] >= pivot) {
                Collections.swap(values, index + 1, i);
                index++;
            }
        }
        Collections.swap(values, start, index);
        if (k <= index - start) {
            qsort(values, start, index - 1, ret, retIndex, k);
        } else {
            for (int i = start; i <= index; i++) {
                ret[retIndex++] = values.get(i)[0];
            }
            if (k > index - start + 1) {
                qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
            }
        }
    }
}