算法第十一天|栈和队列-二叉树

239. 滑动窗口最大值

/**
 * 最大优先级序列----超时
 */
public static int[] maxSlidingWindow1(int[] nums, int k) {
    // 获取一个最大优先级序列
    PriorityQueue<Integer> queue = getMyQueue();
    for (int i = 0; i < k - 1; i++) {
        queue.offer(nums[i]); // 前k-1个元素全部填入
    }

    int[] value = new int[nums.length - k + 1];
    int index = 0;
    for (int i = k - 1; i < nums.length; i++) {
        queue.offer(nums[i]); // 将第k个元素放入
        value[index++] = queue.peek();
        // 去除掉下标为i-k的元素
        queue.remove(nums[i - k + 1]);
    }
    return value;
}

private static PriorityQueue<Integer> getMyQueue() {
    return new PriorityQueue<>((i1, i2) -> {
        if (i1 > i2) {
            return -1;
        } else {
            return 1;
        }
    });
}


/**
 * 
 * 解法2---维护一个递减序列，进行值的增加和减少
 */
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MyDeque myDeque = new MyDeque();
        for (int i = 0; i < k - 1; i++) {
            myDeque.offer(nums[i]);
        }

        int[] value = new int[nums.length - k + 1];
        int index = 0;
        for (int i = k - 1; i < nums.length; i++) {
            myDeque.offer(nums[i]);
            value[index++] = myDeque.peek();
            myDeque.pop(nums[i - k + 1]); // 移除前k个元素
        }
        return value;
    }
}

class MyDeque {
    private Deque<Integer> deque;

    public MyDeque() {
        deque = new LinkedList<>();
    }

    public void offer(int val) {
        // 添加元素
        // 如果不等于空，那么需要和最后一个元素进行比较，如果比最后一个元素更大，那么弹出
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        // 维护了一个从大到小的队列
        deque.offer(val);
    }

    public void pop(int val) {
        // 删除元素,如果传入值和栈顶元素相同，那么就进行删除，否则不做任何操作
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.pop();
        }
    }

    public int peek() {
        return deque.peek();
    }
}

尝试使用优先级序列来做，超时了

解法：维护一个栈，栈顶为最大元素，是一个递减的序列。

347. 前 K 个高频元素

 public static int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }

    List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
    Collections.sort(list, (o1, o2) -> o2.getValue() - o1.getValue());

    int[] value = new int[k];

    int index = 0;
    for (Map.Entry<Integer, Integer> entry : list) {
        if (index >= k) {
            break;
        }
        value[index++] = entry.getKey();
    }
    return value;
}


public static int[] topKFrequent2(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }

    // 两个数组中的第二个值比较，即数组中第一个值为key，第二个为value。大顶堆，栈顶是最大的元素
    PriorityQueue<int[]> queue = new PriorityQueue<>((num0, num1) -> num1[1] - num0[1]);

    int[] value = new int[k];

    int index = 0;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        queue.offer(new int[]{entry.getKey(), entry.getValue()});
    }
    while (!queue.isEmpty() && index < k) {
        int[] poll = queue.poll();
        value[index++] = poll[0];
    }
    return value;
}

方式一使用HashMap来进行统计相同key的个数，再借助Collections工具类对value进行排序输出

排序输出，很容易想到大顶堆（因为是大的先输出）.所以引出方式二

前中后序的迭代遍历

 public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        List<Integer> list = new ArrayList<>();

        while (!stack.isEmpty()) {
            TreeNode top = stack.pop(); // 当前节点
            list.add(top.val);
            if (top.right != null) {
                // 有右子树
                stack.push(top.right);
            }
            if (top.left != null) {
                // 有左子树
                stack.push(top.left);
            }
        }
        return list;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        // 中序遍历,左中右
        List<Integer> result = new ArrayList<>();

        if (root == null){
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop.left != null) {
                // 有左子树
                stack.push(pop.left);
            }
            if (pop.right != null) {
                // 有右子树
                stack.push(pop.right);
            }
            result.add(pop.val);
        }
        return result;
    }

之前使用递归来编写，递归的过程就是将函数压入栈中罢了。那么对应的，可以使用迭代来编写前、中、后序遍历.

不过需要注意的是，我们需要根据递归时压入栈的顺序来操作。