作者： admin

目标

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

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

说明：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

思路

这道题是让我们仅使用push压入栈顶、peek获取栈顶元素、pop弹栈等API实现先进先出队列。

关键是要想明白一点，入栈与出栈操作的是不同的栈，出栈s2中的元素是从入栈s1中获取的，并且，只能在s2为空的时候，将s1中的元素一个个弹栈再入s2，这样才能保证顺序反转。

代码

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @date 2024-03-04 0:42
 */
public class MyQueue {
    private final Deque<Integer> s1;
    private final Deque<Integer> s2;

    public MyQueue() {
        s1 = new ArrayDeque<>();
        s2 = new ArrayDeque<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        if (s2.isEmpty()) {
            throw new RuntimeException();
        }
        return s2.peek();
    }

    public boolean empty() {
        return s2.isEmpty() && s1.isEmpty();
    }
}

Stack注释中有这么一段话，告诉我们应该优先使用Deque接口及其实现。

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

For example: Deque<Integer> stack = new ArrayDeque<Integer>();

在Java中，Stack类是基于Vector实现的，而Vector是一个线程安全的、可动态增长的数组。虽然Stack也是数组实现的，但由于Vector的一些内部机制（例如，每次增长时都会分配更大的数组，并将旧数组的内容复制到新数组中），它可能在某些操作上不如ArrayDeque高效。

相比之下，ArrayDeque是基于循环数组实现的，它避免了不必要的内存分配和复制操作。循环数组意味着当数组的一端达到容量限制时，元素会从另一端开始填充，从而充分利用了数组空间。这种实现方式通常比Vector或Stack更高效。

因此，即使Stack也是数组实现的，但由于Deque（如ArrayDeque）使用了不同的内部机制和优化，它在某些情况下可能会提供更好的性能。

另外，值得注意的是，在Java中，Stack类已经被标记为遗留（legacy），不建议在新的代码中使用。相反，应该使用Deque接口及其实现，如ArrayDeque，因为它们提供了更完整、更一致的操作集合，并且通常具有更好的性能。

性能

时间复杂度：push（数组赋值），empty为O(1)，pop与peek虽然涉及到移动数据，但只有在出栈为空的时候才执行，均摊后为O(1)。

空间复杂度为O(n)。

目标

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

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：

[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

说明：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

思路

这道题的目的是只使用标准库的部分API实现栈，即后进先出。

Java中可以使用Queue接口，offer插入队尾，peek获取队首元素，poll从队首获取并删除元素。

官网给出了两种方法，一种是使用两个队列，offer总是将新元素放到空队列q中，然后将另一队列q1从头至尾放入q，这样就实现了顺序的反转。

例如，依次入栈1，2，3，4：

说明：队首在右边

offer(1)：

q： 1

q1：
----------------------------
offer(2)：

q： 1

q1： 2

q1.offer(q.poll())：

q： 

q1： 1 2
----------------------------
offer(3)：

q： 3

q1： 1 2

while(!q1.isEmpty){q.offer(q1.poll())}：

q： 1 2 3

q1：
----------------------------
offer(4)：

q： 1 2 3

q1： 4

while(!q.isEmpty){q1.offer(q.poll())}：

q：

q1： 1 2 3 4

另一种只用一个队列的方法是：每次offer前先记录队列数据数量n，然后再offer，之后将前面n个数依次poll并offer到队尾。

例如，依次入栈1，2，3，4：

说明：队首在右边

offer(1)：

q： 1

----------------------------
n = 1

offer(2)：

q： 2 1

p.offer(p.poll())：

q： 1 2

----------------------------
n = 2

offer(3)：

q： 3 1 2

循环2次：p.offer(p.poll())

q： 1 2 3

----------------------------
n = 3

offer(4)：

q： 4 1 2 3

循环3次：p.offer(p.poll())

q：1 2 3 4

性能

这两种方法的性能基本相同。

时间复杂度：入栈操作均为O(n)，其余为O(1)。

空间复杂度：O(n)

目标

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

说明：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

思路

虽然这是一道简单题，但是我也想了一个多小时。算法实现起来简单，但是算法的设计，如何得到满足条件的结果也不是那么直观。

说回这道题，要求得最大利润，我们都明白要低买高卖。难道这道题就是让求数组的最大值与最小值？显然不是。我们的目标是求取一个买入点，再其之后的某天卖出获得的利润最大。只能操作一次，可以看成是长线交易（后面还有一道可以多次操作的题）。

暴力解法是遍历股票价格数组，然后向后循环，求得最大利润。时间复杂度是O(n!)，不可行。

思考下面的问题：

取得最大利润是否必须在最低点买入？不是，比如[2,8,1,6]。

取得最大利润是否必须在最高点卖出？不是，比如[3,8,1,7]。

但是，如果遇到了更低的价格，那么它一定是当前最佳的买入点。因为不管后续价格怎么波动，想要获得最大收益，被减数当然越小越好。

因此，问题可以转化为：任取一个买入点，向后遍历并记录最大利润，直到出现一个更低的买入点，在这之前的一段时间内，我们所选的就是最佳买入点，可以记录这段时间内的最大利润。然后以新的最佳买入点继续向后遍历并记录最大利润，直到一个新的最佳买入点出现。在这一过程中如果最大利润比之前的值更大就替换掉。这样我们就得到了问题的答案。

其实，一开始我并没有这么清晰的思路。只是跟着感觉走：

1. 首先，如果遍历时发现股票价格是递减的，那么我们肯定不能买入。这里，我们需要计算后一天减去前一天的收益，如果连着都是负数，那么直接跳过。
2. 然后，如果找到了第一个正收益的点，那么我们买入。之后，我们开始累加收益，这样累加得到的是当天到买入点的收益。即 如果a是我们的买入点，那么往后利润的累加和 profitSum 为 (b - a) + (c - b) + (d - c) + (e - d) = e - a。在这一过程中，我们记录最大收益 profitMax。
3. 接下来，我们需要找到更低的买入点。如果我们的买入点是i，当我们遍历到第j天的时候，profitSum = prices[j] - prices[i]，而当天与前一天的利润为 profit = prices[j] - prices[j-1]，如果profit > profitSum，那么prices[j] - prices[j-1] > prices[j] - prices[i] 即 prices[j-1] < prices[i]。j-1 就是新的最佳买入点。这时我们需要将利润和重置，然后再比较最大利润。

最开始写的时候忽略了查找最新买入点的这个步骤，增加的这个判断 profit > profitSum 是根据错误案例调试出来的，感觉就是如果一天的收益就比之前的历史收益大了，那就没必要再累加前面的利润了，应该重新开始。

代码

/**
 * @date 2024-03-03 1:44
 */
public class MaxProfit {

    public int maxProfit(int[] prices) {
        int profitSum = 0;
        int profitMax = 0;
        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - prices[i - 1];
            if (profitSum <= 0 && profit <= 0) {
                continue;
            }
            profitSum += profit;
            if (profit > profitSum) {
                //  最开始的时候没写这个判断
                profitSum = profit;
            }
            if (profitSum > profitMax) {
                profitMax = profitSum;
            }

        }
        return profitMax;
    }

    public static void main(String[] args) {
        MaxProfit main = new MaxProfit();
        System.out.println(main.maxProfit(new int[]{3, 3, 5, 0, 0, 3, 1, 4}));
    }

}

理清楚之后发现许多操作是没必要的，比如累加每天的利润，实际就是当天价格减去买入点价格。

    public int maxProfit(int[] prices) {
        int buyPoint = 0;
        int profitMax = 0;
        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - prices[buyPoint];
            if (profit <= 0) {
                buyPoint = i;
            } else if (profit > profitMax) {
                profitMax = profit;
            }

        }
        return profitMax;
    }

性能

优化后

目标

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

说明：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路

今天做个简单题吧。要求时间复杂度是O(n)，那么就不能嵌套循环，空间复杂度度是O(1)，也就不能开辟新数组。很自然的可以想到：累加当前出现次数 count 最多的元素 res，如果遇到其它元素则减1，当 count 为负数时，说明当前出现次数最多的元素 可能 发生改变，将res替换为当前元素，并将count置1。

这里说 可能，是因为只要遇到与所选元素值不相等的， count 就减1。我们并不清楚这些其它元素值是否都相同，只能够推出当初所选的多数被其它少数反超了。但是从总体来考虑，如果我们所选择的真是多数元素，那么它一定会在后面再次反超。

官网介绍了一种投票算法 Boyer-Moore，应该也是这种思路吧。

官网还给出了一种分治算法，主要思想是：如果将数组分成两部分，那么数组的众数至少是一部分的众数。递归求解，然后回溯合并，确定子数组众数。不过时间复杂度O(nlog⁡n)，参考算法导论P53主定理。空间复杂度：O(log⁡n)，递归用到的栈空间。

代码

/**
 * @date 2024-03-02 22:24
 */
public class MajorityElement {
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != res) {
                count--;
                // 出错点：反超时应当将值设为1，参考错误用例[10,9,9,9,10]
                if (count < 0) {
                    res = nums[i];
                    count = 1;
                }
            } else {
                count++;
            }
            // 本以为加上可以提高性能，谁知道还慢了2ms
            // if (count > Math.floor(nums.length / 2.0)) {
            //     break;
            // }
        }
        return res;
    }

    public static void main(String[] args) {
        MajorityElement main = new MajorityElement();
        System.out.println(main.majorityElement(new int[]{10, 9, 9, 9, 10}));
    }
}

性能

本以为判断条件可以提高效率，谁知道还慢了2ms，耗时增加了2倍，因为每次算出答案基本上也都循环完了。

目标

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

说明：

• 树中节点数目在范围 [1, 2 * 10^4] 内
• 1 <= Node.val <= 10^5
• 1 <= low <= high <= 10^5
• 所有 Node.val 互不相同

思路

二叉搜索树，也叫二叉查找树（Binary Search Tree, BST）。BST是一颗二叉树，其中的每个节点都含有一个可比较的Key，并且每个节点的Key都大于其左子树中的任意节点的Key，而小于其右子树的任意节点的Key。

比较每个节点是否在给定的范围内，如果节点Key小于low去左子树找，大于high则去右子树找，如果在二者之间，累加和，继续遍历左右子树。

代码

/**
 * @date 2024/2/26 10:37
 */
public class RangeSumBST {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public int sum = 0;

    /** 省去了节点为空的判断嵌套*/
    public int rangeSumBST_v1(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        if (low > root.val) {
            rangeSumBST_v1(root.right, low, high);
        }
        if (high < root.val) {
            rangeSumBST_v1(root.left, low, high);
        }
        if (high >= root.val && low <= root.val) {
            sum += root.val;
            rangeSumBST_v1(root.left, low, high);
            rangeSumBST_v1(root.right, low, high);
        }
        return sum;
    }

    public int rangeSumBST(TreeNode root, int low, int high) {
        if (low > root.val) {
            if (root.right != null) {
                rangeSumBST(root.right, low, high);
            }
        }
        if (high < root.val) {
            if (root.left != null) {
                rangeSumBST(root.left, low, high);
            }
        }
        if (high >= root.val && low <= root.val){
            sum += root.val;
            if (root.left != null) {
                rangeSumBST(root.left, low, high);
            }
            if (root.right != null) {
                rangeSumBST(root.right, low, high);
            }
        }
        return sum;
    }
}

性能