月度归档： 2025 年 2 月

目标

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

• BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
• void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
• string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
• string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

示例：

输入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

说明：

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage 和 url 都只包含 '.' 或者小写英文字母。
• 最多调用 5000 次 visit， back 和 forward 函数。

思路

设计一个浏览器历史记录管理器，记录在同一个标签页的浏览历史，允许前进/后退 steps 步（不能超出浏览记录的范围）。如果打开新页面，当前页面记录会覆盖前进的记录。

使用栈模拟，记录 cur 与 tail 两个指针，前进取 Math.min(tail, cur + steps)，后退取 Math.max(0, cur - steps)，访问新页面 ++cur; tail = cur;。

代码

/**
 * @date 2025-02-26 8:48
 */
class BrowserHistory {

    String[] history = new String[5000];
    int tail = 0;
    int cur = 0;

    public BrowserHistory(String homepage) {
        history[0] = homepage;
    }

    public void visit(String url) {
        history[++cur] = url;
        tail = cur;
    }

    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return history[cur];
    }

    public String forward(int steps) {
        cur = Math.min(tail, cur + steps);
        return history[cur];
    }
}

性能

目标

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

示例 1：

输入：[[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

示例 2：

输入：arrays = [[1],[1]]
输出：0

说明：

• m == arrays.length
• 2 <= m <= 10^5
• 1 <= arrays[i].length <= 500
• -10^4 <= arrays[i][j] <= 10^4
• arrays[i] 以 升序 排序。
• 所有数组中最多有 10^5 个整数。

思路

有一个二维数组，其中的每个数组都按升序排列。任选其中两个数组，从每个数组中选两个元素，求这两个元素距离的最大值，距离指差的绝对值。

显然应该选取最大值与最小值的差，但题目限制是从两个数组中取。我们可以求得最大与次最大、最小与次最小，同时记录所属数组。

如果有多个最值相同，从哪个数组中取有影响吗？由于我们从每个组只取首尾两个元素，最值与次最值一定来自不同的组，所以最值的比较可以使用 >= 和 <=。如果最值来自相同的组，那么只需比较最大值与次最小值，次最大值与最小值。

网友题解使用变量记录前面的最大与最小值，那么最大距离为 Math.max(res, Math.max(curMax - preMin, preMax - curMin))。

代码

/**
 * @date 2025-02-19 8:57
 */
public class MaxDistance624 {

    public int maxDistance_v1(List<List<Integer>> arrays) {
        int res = 0;
        int preMax = Integer.MIN_VALUE / 2;
        int preMin = Integer.MAX_VALUE / 2;
        for (List<Integer> array : arrays) {
            int n = array.size();
            Integer curMax = array.get(n - 1);
            Integer curMin = array.get(0);
            res = Math.max(res, Math.max(curMax - preMin, preMax - curMin));
            preMax = Math.max(preMax, curMax);
            preMin = Math.min(preMin, curMin);
        }
        return res;
    }

    public int maxDistance(List<List<Integer>> arrays) {
        int[] max = new int[]{Integer.MIN_VALUE, -1};
        int secondMax = Integer.MIN_VALUE;
        int[] min = new int[]{Integer.MAX_VALUE, -1};
        int secondMin = Integer.MAX_VALUE;
        for (int i = 0; i < arrays.size(); i++) {
            List<Integer> array = arrays.get(i);
            int n = array.size();
            if (min[0] >= array.get(0)) {
                secondMin = min[0];
                min[0] = array.get(0);
                min[1] = i;
            } else if (secondMin > array.get(0)) {
                secondMin = array.get(0);
            }
            if (max[0] <= array.get(n - 1)) {
                secondMax = max[0];
                max[0] = array.get(n - 1);
                max[1] = i;
            } else if (secondMax < array.get(n - 1)) {
                secondMax = array.get(n - 1);
            }
        }
        if (max[1] != min[1]) {
            return max[0] - min[0];
        } else {
            return Math.max(max[0] - secondMin, secondMax - min[0]);
        }
    }

}

性能