头像

wzc1995


访客:446403

离线:4小时前



wzc1995
1天前

题目描述

给定一个字符串 num 和一个整数 k。其中,num 表示一个很大的整数,字符串中的每个字符依次对应整数上的各个 数位

你可以交换这个整数相邻数位的数字 最多 k 次。

请你返回你能得到的最小整数,并以字符串形式返回。

样例

q4_1.jpg

输入:num = "4321", k = 4
输出:"1342"
解释:4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。
输入:num = "100", k = 1
输出:"010"
解释:输出可以包含前导 0 ,但输入保证不会有前导 0。
输入:num = "36789", k = 1000
输出:"36789"
解释:不需要做任何交换。
输入:num = "22", k = 22
输出:"22"
输入:num = "9438957234785635408", k = 23
输出:"0345989723478563548"

限制

  • 1 <= num.length <= 30000
  • num 只包含 数字 且不含有 前导 0
  • 1 <= k <= 10^9

算法

(贪心,树状数组) $O(n \log n)$
  1. 贪心的规则是每次尽可能的取一个小的数字放到最前。
  2. 首先将每个数字的位置存放在一个队列中。
  3. 从最高位开始填数字,从小到大枚举数字,并计算填当前数字所需要的最少步数。
  4. 最小步数等于数字的原下标减去偏移量,其中偏移量为原下标小于该数字下标,且被使用过的数字的个数。
  5. 偏移量的计算可以通过树状数组来解决,树状数组维护前缀和,如果使用了当前数字,就在当前数字的下标上累加 1。查询时,直接查询当前下标的前缀和。
  6. 注意,代码中树状数组的下标是从 1 开始的。

时间复杂度

  • 每个位置最多需要枚举 10 次,枚举的每次需要查询或更新树状数组。
  • 故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储每个数字的下标队列和树状数组。

C++ 代码

class Solution {
private:
    vector<int> f;

    void update(int x, int n, int y) {
        for (; x <= n; x += x & -x)
            f[x] += y;
    }

    int query(int x) {
        int tot = 0;
        for (; x; x -= x & -x)
            tot += f[x];

        return tot;
    }

public:
    string minInteger(string num, int k) {
        int n = num.size();
        vector<queue<int>> v(10);

        for (int i = 0; i < n; i++)
            v[num[i] - '0'].push(i);

        f.resize(n + 1, 0);

        for (int i = 0; i < n; i++)
            for (int d = 0; d < 10; d++) {
                if (v[d].empty()) continue;
                int x = v[d].front();
                int offset = query(x + 1);

                if (x - offset <= k) {
                    num[i] = d + '0';
                    k -= x - offset;
                    update(x + 1, n, 1);

                    v[d].pop();
                    break;
                }
            }

        return num;
    }
};



wzc1995
1天前

题目描述

给定一个只包含 0 和 1 的 rows * columns 矩阵 mat,请你返回有多少个 子矩形 的元素全部都是 1。

样例

输入:mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出:13
解释:
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13。
输入:mat = [[0,1,1,0],
            [0,1,1,1],
            [1,1,1,0]]
输出:24
解释:
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24。
输入:mat = [[1,1,1,1,1,1]]
输出:21
输入:mat = [[1,0,1],[0,1,0],[1,0,1]]
输出:5

限制

  • 1 <= rows <= 150
  • 1 <= columns <= 150
  • 0 <= mat[i][j] <= 1

算法1

(暴力枚举) $O(n^3)$
  1. 枚举起始行 $i$,然后按顺序枚举终止行 $j$。对于第 $k$ 列,如果第 $i$ 行到第 $j$ 行都是 1,则令 $v_k := true$。否则 $v_k := false$。$v$ 数组可以动态维护。
  2. 固定 $i$ 和 $j$ 以及得到 $v$ 数组之后,统计以每一列结尾的矩形有多少个,即统计以每个 $k$ 结尾的最大连续的 $true$ 有多少,累计答案。

时间复杂度

  • 枚举 $i$ 和 $j$ 需要 $O(n^2)$ 的时间,每次需要 $O(n)$ 的时间遍历每一列,故总时间复杂度为 $O(n^3)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储 $v$ 数组。

C++ 代码

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int r = mat.size(), c = mat[0].size();
        int ans = 0;

        for (int i = 0; i < r; i++) {
            vector<bool> v(c, true);

            for (int j = i; j < r; j++) {
                for (int k = 0; k < c; k++)
                    if (mat[j][k] == 0)
                        v[k] = false;

                for (int tot = 0, k = 0; k < c; k++) {
                    if (v[k] == false) {
                        tot = 0;
                    } else {
                        tot++;
                        ans += tot;
                    }
                }
            }
        }

        return ans;
    }
};

算法2

(单调栈) $O(n^2)$
  1. 考虑一维的问题,假设给定了一个一维数组,每个元素的值代表当前位置的高度,求总共有多少个矩形。我们按行分解来解决这个问题。
  2. 我们按顺序遍历数组,然后维护一个严格单调递增的栈。如果当前高度 $v_j$ 小于等于 栈顶元素 $v_{top}$,则栈顶元素出栈。出栈后,$j$ 和新的栈顶元素 $st(top)$ 分别是 $top$ 两侧第一个严格比其低的位置。基于此,我们需要计算在 $top$ 比其两侧高的部分贡献的答案。然后当前位置 $j$ 进栈。
  3. 此时矩形的高度为 $h := v_{top} - \max{(v_j, v_{st(top)})}$,最大 宽度为 $w := j - st(top) - 1$。所有以 $top$ 为右端点的宽度都需要计算。所以贡献的答案为 $h * (w + 1) * w / 2$。
  4. 最后还在栈中的元素,按照假设最后还有一个高度为 0 的哨兵元素来进行出栈操作。这个一维问题的算法仅需要线性的时间。
  5. 此问题可以看做 $n$ 个一维问题,即记录下每一行中,每一列向上连续的 1 的最大高度 $v_j$。

时间复杂度

  • 对于每一行,每个位置都仅进栈一次,出栈一次,故总时间复杂度为 $O(n^2)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储每一列的有效高度和单调栈。

C++ 代码

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int r = mat.size(), c = mat[0].size();
        int ans = 0;
        vector<int> v(c + 1, 0);

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++)
                v[j] = mat[i][j] == 0 ? 0 : v[j] + 1;

            stack<int> st;
            for (int j = 0; j <= c; j++) {
                while (!st.empty() && v[j] <= v[st.top()]) {
                    int top = st.top();
                    st.pop();

                    int h, w;
                    if (st.empty()) {
                        h = v[top] - v[j];
                        w = j;
                    } else {
                        h = v[top] - max(v[j], v[st.top()]);
                        w = j - st.top() - 1;
                    }

                    ans += h * (w + 1) * w / 2;
                }

                st.push(j);
            }
        }

        return ans;
    }
};



wzc1995
1天前

题目描述

有一块木板,长度为 n单位。一些蚂蚁在木板上移动,每只蚂蚁都以 每秒一个单位 的速度移动。其中,一部分蚂蚁向 移动,其他蚂蚁向 移动。

当两只向 不同 方向移动的蚂蚁在某个点相遇时,它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时,它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

样例

ants.jpg

输入:n = 4, left = [4,3], right = [0,1]
输出:4
解释:如上图所示:
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意,蚂蚁在木板上的最后时刻是 t = 4 秒,之后蚂蚁立即从木板上掉下来。
(也就是说在 t = 4.0000000001 时,木板上没有蚂蚁)。

ants2.jpg

输入:n = 7, left = [], right = [0,1,2,3,4,5,6,7]
输出:7
解释:所有蚂蚁都向右移动,下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

ants3.jpg

输入:n = 7, left = [0,1,2,3,4,5,6,7], right = []
输出:7
解释:所有蚂蚁都向左移动,下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
输入:n = 9, left = [5], right = [4]
输出:5
解释:t = 1 秒时,两只蚂蚁将回到初始位置,但移动方向与之前相反。
输入:n = 6, left = [6], right = [0]
输出:6

限制

  • 1 <= n <= 10^4
  • 0 <= left.length <= n + 1
  • 0 <= left[i] <= n
  • 0 <= right.length <= n + 1
  • 0 <= right[i] <= n
  • 1 <= left.length + right.length <= n + 1
  • leftright 中的所有值都是唯一的,并且每个值 只能出现在二者之一 中。

算法

(模拟) $O(n)$
  1. 两只蚂蚁相遇可以忽略,因为交换方向如果不考虑蚂蚁编号的话实际上等于没有交换。
  2. 对于向左走的蚂蚁,需要的时间等于初始的位置;对于向右走的蚂蚁,需要的时间等于长度减去初始位置。

时间复杂度

  • 分别遍历两个数组一次,时间复杂度为 $O(n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans = 0;
        for (int x : left)
            ans = max(ans, x);

        for (int x : right)
            ans = max(ans, n - x);

        return ans;
    }
};



wzc1995
1天前

题目描述

给你一个数字数组 arr

如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列

如果可以重新排列数组形成等差数列,请返回 true;否则,返回 false

样例

输入:arr = [3,5,1]
输出:true
解释:对数组重新排序得到 [1,3,5] 或者 [5,3,1],
任意相邻两项的差分别为 2 或 -2,可以形成等差数列。
输入:arr = [1,2,4]
输出:false
解释:无法通过重新排序得到等差数列。

限制

  • 2 <= arr.length <= 1000
  • -10^6 <= arr[i] <= 10^6

算法

(排序) $O(n \log n)$
  1. 将原数组从小到大排序。
  2. 判断任意相邻两个数字的差值是否一致。

时间复杂度

  • 排序后遍历一次,故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        int n = arr.size(), d = arr[1] - arr[0];

        for (int i = 2; i < n; i++)
            if (arr[i] - arr[i - 1] != d)
                return false;

        return true;
    }
};



wzc1995
7天前

题目描述

给定一组 N 人(编号为 1, 2, ..., N),我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人,那么他们不应该属于同一组。

形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 ab 的人归入同一组。

当可以用这种方法将每个人分进两组时,返回 true;否则返回 false

样例

输入:N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出:true
解释:group1 [1,4], group2 [2,3]
输入:N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出:false
输入:N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出:false

限制

  • 1 <= N <= 2000
  • 0 <= dislikes.length <= 10000
  • dislikes[i].length == 2
  • 1 <= dislikes[i][j] <= N
  • dislikes[i][0] < dislikes[i][1]
  • 对于 dislikes[i] == dislikes[j] 不存在 i != j

算法

(二分图判定,黑白染色) $O(n + m)$
  1. 用黑白两种颜色对整个图进行染色,相邻的结点染不同的颜色。
  2. 如果过程中出现相邻两个结点颜色一样,则说明出现了奇环。
  3. 图论告诉我们有奇环的图不是二分图。

时间复杂度

  • 需要遍历整个图进行染色,故时间复杂度为 $O(n + m)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储遍历用的数据结构。

C++ 代码 (DFS)

class Solution {
private:
    bool dfs(int u, const vector<vector<int>> &graph, vector<int> &col) {
        for (int v : graph[u])
            if (col[v] == -1) {
                col[v] = 1 - col[u];
                if (!dfs(v, graph, col))
                    return false;
            } else if (col[v] == col[u])
                return false;

        return true;
    }
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(N);
        for (const auto &v : dislikes) {
            int x = v[0] - 1, y = v[1] - 1;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        vector<int> col(N, -1);

        for (int i = 0; i < N; i++)
            if (col[i] == -1) {
                col[i] = 0;
                if (!dfs(i, graph, col))
                    return false;
            }

        return true;
    }
};

C++ 代码 (BFS)

class Solution {
private:
    bool bfs(int S, const vector<vector<int>> &graph, vector<int> &col) {
        queue<int> q;

        q.push(S);
        col[S] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : graph[u]) {
                if (col[v] == col[u])
                    return false;
                if (col[v] == -1) {
                    col[v] = 1 - col[u];
                    q.push(v);
                }
            }
        }

        return true;
    }

public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(N);
        for (const auto &v : dislikes) {
            int x = v[0] - 1, y = v[1] - 1;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        vector<int> col(N, -1);

        for (int i = 0; i < N; i++)
            if (col[i] == -1)
                if (!bfs(i, graph, col))
                    return false;

        return true;
    }
};



wzc1995
7天前

题目描述

i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit

每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

样例

输入:people = [1,2], limit = 3
输出:1
解释:1 艘船载 (1, 2)
输入:people = [3,2,2,1], limit = 3
输出:3
解释:3 艘船分别载 (1, 2), (2) 和 (3)
输入:people = [3,5,3,4], limit = 5
输出:4
解释:4 艘船分别载 (3), (3), (4), (5)

限制

  • 1 <= people.length <= 50000
  • 1 <= people[i] <= limit <= 30000

算法

(贪心) $O(n \log n)$
  1. 将人按重量排序。
  2. 如果当前最重的人和当前最轻的人能坐到一条船上,则他们坐一条船。否则当前最重的人单独坐一条船走。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 排序后,每个人仅需要遍历一次,故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());

        int i = 0, j = people.size() - 1, ans = 0;
        while (i <= j) {
            if (i != j && people[i] + people[j] <= limit)
                i++;

            j--;
            ans++;
        }

        return ans;
    }
};



wzc1995
7天前

题目描述

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K(单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 KK 为整数)。

样例

输入:piles = [3,6,7,11], H = 8
输出:4
输入:piles = [30,11,23,4,20], H = 5
输出:30
输入:piles = [30,11,23,4,20], H = 6
输出:23

限制

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

算法

(二分答案) $O(n \log M)$
  1. 注意到 K 越小,所花费的时间越长,我们要找到一个最小的 K 满足花费的时间小于等于 H
  2. 二分查找这个 K 值,如果花费的时间小于等于 H,我们就继续减小 K。否则我们增大 K。二分的范围从 1 到数组中的最大值 $M$。

时间复杂度

  • 二分的次数为 $O(\log M)$。
  • 每次二分需要线性的时间判定,故总时间复杂度为 $O(n \log M)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    int calc(int k, const vector<int> &piles) {
        int tot = 0;
        for (int x : piles)
            tot += x / k + (bool)(x % k);

        return tot;
    }

public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int n = piles.size();
        int l = 1;
        int r = *max_element(piles.begin(), piles.end());

        while (l < r) {
            int mid = (l + r) >> 1;
            if (calc(mid, piles) <= H) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};



wzc1995
7天前

题目描述

如果序列 X_1, X_2, ..., X_n 满足下列条件,就说它是 斐波那契式 的:

  • n >= 3
  • 对于所有 i + 2 <= n,都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列,找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在,返回 0

(回想一下,子序列是从原序列 A 中派生出来的,它从 A 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如,[3, 5, 8][3, 4, 5, 6, 7, 8] 的一个子序列)

样例

输入:[1,2,3,4,5,6,7,8]
输出:5
解释:
最长的斐波那契式子序列为:[1,2,3,5,8]。
输入:[1,3,7,11,12,14,18]
输出:3
解释:
最长的斐波那契式子序列有:
[1,11,12],[3,11,14] 以及 [7,11,18]。

限制

  • 3 <= A.length <= 1000
  • 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
    *(对于以 Java,C,C++,以及 C# 的提交,时间限制被减少了 50%)

算法1

(暴力枚举) $O(n^2 \log M)$
  1. 枚举斐波那契数列的前两个数字,然后用集合暴力判定数列能延续的长度。
  2. 因为斐波那契数列上升是指数级的,所以答案最多不超过 $O(\log M)$,其中 $M$ 是最大的数字。
  3. 我们可以加上一个剪枝,如果第一个数字的 ans + 2 倍超过了数组中最大的数字,则此次判定必定不会超过当前答案。

时间复杂度

  • 枚举开头两个数字的时间复杂度为 $O(n^2)$。
  • 暴力判定的时间复杂度为 $O(\log M)$。
  • 故总时间复杂度为 $O(n^2 \log M)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储集合。

C++ 代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        unordered_set<int> nums(A.begin(), A.end());
        int n = A.size();

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int x = A[i], y = A[j];

                if ((long long)(x) * (ans + 2) > A.back())
                    continue;

                int cnt = 0;
                while (nums.find(x + y) != nums.end()) {
                    cnt++;
                    int t = x + y;
                    x = y; y = t;
                }

                ans = max(ans, cnt);
            }

        return ans == 0 ? 0 : ans + 2;
    }
};

算法2

(动态规划) $O(n^2)$
  1. 设状态 $f(i, j)$ 表示以 nums[i]nums[j] 结尾的斐波那契数列的最大长度,其中 $i < j$。
  2. 初始化全部为 0。
  3. 转移时,如果存在一个下标 $k$,满足 $k < i$ 且 $nums[k] = nums[j] - nums[i]$,则转移 $f(i, j) = f(k, i) + 1$,这一步可以用哈希表判定。
  4. 最终答案为 $f$ 数组中的最大值。

时间复杂度

  • 状态数为 $O(n^2)$,每次转移仅需要常数时间,故总时间复杂度为 $O(n^2)$。

空间复杂度

  • 需要 $O(n^2)$ 的额外空间存储哈希表和动态规划的状态。

C++ 代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> f(n, vector<int>(n, 0));

        unordered_map<int, int> mp;
        for (int i = 0; i < n; i++)
            mp[A[i]] = i;

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int d = A[j] - A[i];
                if (mp.find(d) != mp.end() && mp[d] < i) {
                    f[i][j] = f[mp[d]][i] + 1;
                    ans = max(ans, f[i][j]);
                }
            }

        return ans == 0 ? 0 : ans + 2;
    }
};



wzc1995
7天前

题目描述

给定两个大小相等的数组 ABA 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列,使其相对于 B 的优势最大化。

样例

输入:A = [2,7,11,15], B = [1,10,4,11]
输出:[2,11,7,15]
输入:A = [12,24,8,32], B = [13,25,32,11]
输出:[24,32,8,12]

限制

  • 1 <= A.length = B.length <= 10000
  • 0 <= A[i] <= 10^9
  • 0 <= B[i] <= 10^9

算法

(贪心) $O(n \log n)$
  1. AB 数组从小到大排序。
  2. B 数组上定义双指针 lr,初始时 l = 0r = n - 1。如果当前 A[i] > B[l],则我们就这样安排,否则我们安排当前 B 最大的数字。
  3. 贪心的正确性是 A 中的每个数字都要尽可能的干掉 B 中的一个数字,如果干不掉,则消耗掉 B 中剩余最大的数字。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 安排数字的时间复杂度为 $O(n)$。
  • 故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储 B 数组的索引和答案。

C++ 代码

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> idx(n);

        for (int i = 0; i < n; i++)
            idx[i] = i;

        sort(A.begin(), A.end());
        sort(idx.begin(), idx.end(), [&](int x, int y) {
            return B[x] < B[y];
        });

        vector<int> ans(n);

        for (int i = 0, l = 0, r = n - 1; i < n; i++) {
            if (A[i] > B[idx[l]]) ans[idx[l++]] = A[i];
            else ans[idx[r--]] = A[i];
        }

        return ans;
    }
};



wzc1995
8天前

题目描述

给定一个数组 points 和一个整数 k。数组中每个元素都表示二维平面上的点的坐标,并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [x_i, y_i],并且在 1 <= i < j <= points.length 的前提下,x_i < x_j 总成立。

请你找出 y_i + y_j + |x_i - x_j|最大值,其中 |x_i - x_j| <= k1 <= i < j <= points.length

题目测试数据保证至少存在一对能够满足 |x_i - x_j| <= k 的点。

样例

输入:points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出:4
解释:前两个点满足 |xi - xj| <= 1 ,带入方程计算,则得到值 3 + 0 + |1 - 2| = 4。
第三个和第四个点也满足条件,得到值 10 + -10 + |5 - 6| = 1。
没有其他满足条件的点,所以返回 4 和 1 中最大的那个。
输入:points = [[0,0],[3,0],[9,2]], k = 3
输出:3
解释:只有前两个点满足 x 坐标差的绝对值小于 3,带入后得到值 0 + 0 + |0 - 3| = 3。

限制

  • 2 <= points.length <= 10^5
  • points[i].length == 2
  • -10^8 <= points[i][0], points[i][1] <= 10^8
  • 0 <= k <= 2 * 10^8
  • 对于所有的 1 <= i < j <= points.lengthpoints[i][0] < points[j][0] 都成立。
  • x_i 是严格递增的。

算法

(单调队列) $O(n)$
  1. 假定 $x_i < x_j$,将原方程进行变形,得到 $(y_i - x_i) + (y_j + x_j)$。可以枚举每一个 $y_j + x_j$,找到 $i < j$,使得 $y_i - x_i$ 尽可能大。
  2. 维护一个从队头到队尾严格单调递减的队列,队列中存下标。
  3. 如果当前队头元素不满足限制,则队头不断出队。
  4. 如果队列非空,则用队头更新答案。
  5. 如果当前 $y_j - x_j$ 大于等于队尾,则队尾不断出队,因为出队的元素都不如 $j$ 更优。
  6. 最后 $j$ 入队。

时间复杂度

  • 每个位置最多入队一次,出队一次,故时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储队列。

C++ 代码

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int n = points.size();
        deque<int> q;
        int ans = INT_MIN;

        for (int j = 0; j < n; j++) {
            int xj = points[j][0], yj = points[j][1];

            while (!q.empty() && xj - points[q.front()][0] > k)
                q.pop_front();

            if (!q.empty()) {
                int i = q.front();
                ans = max(ans, points[i][1] - points[i][0] + yj + xj);
            }

            while (!q.empty() && yj - xj >= points[q.back()][1] - points[q.back()][0])
                q.pop_back();

            q.push_back(j);
        }

        return ans;
    }
};