蔚来
近日，著名职场爆料社区「脉脉」有蔚来内部员工爆料今年年终奖的情况。
三星 + 三星：0.2 个月 三星 + 四星：0.35 个月 四星 + 四星：0.5 个月 四星 + 五星：0.7 个月 五星 + 五星：1 个月
获得"几个几星"的难度，我们无从知晓，但从「最高级别的年终实也就 1 个月」来看，今年蔚来今年过得一般 🤣🤣🤣
在现在内卷到极致的新能源赛道，销量好未必代表财务数据好。
在刚过去的 2024 年，蔚来以 20.53 万的销量在「新势力品牌」销量榜中排名第五。
第一感觉还可以，毕竟都进前五了，但如果放到更大的盘子，例如「新能源品牌」销量榜中，蔚来连前 10 都进不去，甚至只有断层王者比亚迪的 1/15 的水平。
要知道，蔚来可是一家有着十年历史的车企。
在过去 10 年里，蔚来烧掉了 1000 亿，比特斯拉能烧多了，但销量却一直平平。也是因为这样的同行的存在，只花了 300 亿就搞出了一款爆款轿车的小米汽车含金量还在上升。
对此，你怎么看？你身边有蔚来车主吗？欢迎评论区交流。
...
回归主题。
来一道和「校招」相关的算法题。
题目描述
平台：LeetCode
题号：436
给你一个区间数组 intervals ，其中 ，且每个 都 不同 。
区间 的 右侧区间 可以记作区间 ，并满足 ，且 最小化 。
返回一个由每个区间 的 右侧区间 的最小起始位置组成的数组。如果某个区间 不存在对应的 右侧区间 ，则下标 处的值设为 。
示例 1：
输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。
示例 2：
输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。
示例 3：
输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
提示：
每个间隔的起点都 不相同
排序 + 二分
为了方便，我们称 为 。
对于每个 而言，我们需要在所有满足「」中找到 值最小的下标 ，并将其记为 。
对于一个特定的 而言，其右端点固定，并且我们只关心目标位置的左端点。
因此我们可以构造一个记录区间左端点的数组 ，并将其进行排序，同时为了记录每个左端点来自于原序列中的那个下标，还需要额外记录原序列下标，即以 二元组的形式进行转存，并根据 排序。
然后从前往后处理每个 ，运用「二分」在 中找到第一个满足左端点 大于等于 的成员 ，将其 即是 的最右区间。
Java 代码：
class Solution {
public int[] findRightInterval(int[][] its) {
int n = its.length;
int[][] clone = new int[n][2];
for (int i = 0; i < n; i++) clone[i] = new int[]{its[i][0], i};
Arrays.sort(clone, (a,b)->a[0]-b[0]);
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (clone[mid][0] >= its[i][1]) r = mid;
else l = mid + 1;
}
ans[i] = clone[r][0] >= its[i][1] ? clone[r][1] : -1;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& its) {
int n = its.size();
vector<pair<int, int>> clone;
clone.reserve(n);
for (int i = 0; i < n; i++) clone.push_back({its[i][0], i});
sort(clone.begin(), clone.end());
vector<int> ans(n);
for (int i = 0; i < n; i++) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (clone[mid].first >= its[i][1]) r = mid;
else l = mid + 1;
}
ans[i] = (clone[r].first >= its[i][1]) ? clone[r].second : -1;
}
return ans;
}
};
Python 代码：
class Solution:
def findRightInterval(self, its: List[List[int]]) -> List[int]:
n = len(its)
clone = [(its[i][0], i) for i in range(n)]
clone.sort()
ans = []
for i in range(n):
l, r = 0, n - 1
while l < r:
mid = l + r >> 1
if clone[mid][0] >= its[i][1]:
r = mid
else:
l = mid + 1
ans.append(clone[r][1] if clone[r][0] >= its[i][1] else -1)
return ans
TypeScript 代码：
function findRightInterval(its: number[][]): number[] {
const n = its.length;
const clone: [number, number][] = its.map(([start, _], i) => [start, i]);
clone.sort((a, b) => a[0] - b[0]);
const ans: number[] = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
let l = 0, r = n - 1;
while (l < r) {
const mid = l + r >> 1;
if (clone[mid][0] >= its[i][1]) r = mid;
else l = mid + 1;
}
ans[i] = clone[r][0] >= its[i][1] ? clone[r][1] : -1;
}
return ans;
};
时间复杂度：排序复杂度为 ；对于每个 找到最右区间需要进行二分，复杂度为 。整体复杂度为 空间复杂度：
双指针（莫队思想）
更进一步，在解法一中我们并没有对求解询问的顺序进行调整，这导致了我们不得不每次都在整个左端点序列中进行二分。
朴素处理询问的方式，需要每次对整个序列进行扫描，复杂度为 。
实际上，如果我们按照「右端点从小到大」的顺序处理询问，其每个询问对应的「最右区间的左端点」也具有单调特性。
因此，我们可以运用莫队思想：通过调整询问的处理顺序，来减少扫描目标位置的指针移动次数。将其从「必然进行 次移动」优化为「最多不超过 次移动」，从而将 构造答案 的复杂度从 优化为 。
最后，由于每个 只关心目标位置的「左端点」，因此我们无须对某一段进行分块，而直接使用双指针实现即可。
Java 代码：
class Solution {
public int[] findRightInterval(int[][] its) {
int n = its.length;
int[][] ss = new int[n][2], es = new int[n][2];
for (int i = 0; i < n; i++) {
ss[i] = new int[]{its[i][0], i};
es[i] = new int[]{its[i][1], i};
}
Arrays.sort(ss, (a,b)->a[0]-b[0]);
Arrays.sort(es, (a,b)->a[0]-b[0]);
int[] ans = new int[n];
for (int i = 0, j = 0; i < n; i++) {
int[] cur = es[i];
int loc = cur[0], idx = cur[1];
while (j < n && ss[j][0] < loc) j++;
ans[idx] = j == n ? -1 : ss[j][1];
}
return ans;
}
}
C++ 代码：
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& its) {
int n = its.size();
vector<pair<int, int>> ss, es;
for (int i = 0; i < n; i++) {
ss.push_back({its[i][0], i});
es.push_back({its[i][1], i});
}
sort(ss.begin(), ss.end());
sort(es.begin(), es.end());
vector<int> ans(n, -1);
for (int i = 0, j = 0; i < n; i++) {
auto cur = es[i];
int loc = cur.first, idx = cur.second;
while (j < n && ss[j].first < loc) j++;
ans[idx] = (j == n) ? -1 : ss[j].second;
}
return ans;
}
};
Python 代码：
class Solution:
def findRightInterval(self, its: List[List[int]]) -> List[int]:
n = len(its)
ss = [(its[i][0], i) for i in range(n)]
es = [(its[i][1], i) for i in range(n)]
ss.sort()
es.sort()
ans = [-1] * n
j = 0
for i in range(n):
cur = es[i]
loc, idx = cur[0], cur[1]
while j < n and ss[j][0] < loc:
j += 1
ans[idx] = -1 if j == n else ss[j][1]
return ans
TypeScript 代码：
function findRightInterval(its: number[][]): number[] {
const n = its.length;
const ss = its.map(([start, _], i) => [start, i]);
const es = its.map(([_, end], i) => [end, i]);
ss.sort((a, b) => a[0] - b[0]);
es.sort((a, b) => a[0] - b[0]);
const ans = new Array(n).fill(-1);
for (let i = 0, j = 0; i < n; i++) {
const [loc, idx] = es[i];
while (j < n && ss[j][0] < loc) j++;
ans[idx] = j == n ? -1 : ss[j][1];
}
return ans;
};
时间复杂度：排序复杂度为 ；双指针构造答案的复杂度为 。整体复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
