Python技术迷

面试上一个神仙公司,运维50岁了,其他研发也45多了。公司不裁员,只要好好干活就行。我打算进去了,今年35岁了,是不是进入有点早

刚看到个贴子,说网友面试到一家“神仙公司”,运维50岁还在干,研发45岁也稳稳当当,公司不裁员,只要好好干活就行。楼主35岁就想进去,还担心是不是去早了,哈哈这心态挺真实。

Image

网友回帖里有人说这种公司稳定但天花板低,也有人说能干到老是福气。嗯…我觉得关键还是看你图啥。如果你追求稳定、节奏正常,那这种环境就像早上排队买早餐,虽然慢点,但排到了心安;但要是你还想折腾、想冲晋升,那可能会觉得节奏太稳像坐慢车。

换个角度想,35岁进稳定公司绝对不算早,反而是刚刚合适。比起盲卷,能找到一个踏实干活的地方,本身就是稀缺资源。说到底还是性价比的问题——岗位稳、团队成熟、风险低,这些对职场中后期的人太重要了。【备注:文末可领最新资料】

面试题:天际线问题

说“天际线问题”这个名字挺浪漫的哈,但本质就是个很典型的扫线+堆的算法题,用 Python 写起来也不算难,就是第一次接触会有点绕,我慢慢聊一遍。

想象你站在城市对面河边,看过去一排高楼,能看到的轮廓线就是“天际线”。 题目一般给你一堆楼,每栋楼用三个数表示:

[L, R, H]
L:左边界 x 坐标
R:右边界 x 坐标
H:高度

所有楼都紧贴地面,相互之间可以重叠。我们要输出的是一串“关键点”:

[x, h]
x:从这个 x 开始,最高楼的高度变成 h

串起来就是天际线的折线图。比如有一段高度从 0 → 3 → 5 → 0,那我们就要在高度变化的地方记录点。

暴力想法为什么不行

很多人第一反应是:要不我把所有 x 都离散化一遍,比如从最小 L 到最大 R,每个单位点都算一下当前最高楼,然后再把这些高度压成折线?

问题是:

  • 坐标可能很大,比如到 10^9,你根本不可能从 0 枚举到 10^9
  • 即便离散化,只要楼很多,这样扫一整条 x 轴也是 O(坐标范围) 的复杂度,直接超时

所以正确的方向是:我只关心“高度会变的那些 x”,中间那些高度不变的地方完全可以跳过。

扫描线的基本思路

比较经典的套路就是“扫描线”:

  1. 想象一根竖直的线,从左往右扫过整个平面
  2. 每到一个“关键 x”,我们更新一下当前有哪些楼是“活跃的”(覆盖到当前 x)
  3. 随时维护一个“当前最高楼高度”
  4. 一旦最高高度发生变化,就把 [x, 当前最高高度] 记下来

关键问题有两个:

  • 怎么表示这些“关键 x”
  • 怎么快速知道“当前最高楼高度”

把楼拆成一堆“事件”

每栋楼 [L, R, H],我们可以拆成两个事件:

  • 在 x = L 处,这栋楼开始生效
  • 在 x = R 处,这栋楼结束

于是我们构造一个数组:

(L, -H, R)  # 楼开始:高度取负数是个小技巧
(R, 0, 0)   # 楼结束:高度为 0,表示只是一个结束标记

为啥高度要取负数?

因为 Python 的 heapq 是小根堆,而我们想要“最高的楼”,所以把高度取负数,这样“原来越高的楼,负数越小”,放在堆顶刚刚好。

然后我们把所有事件按照 x 排序:

  • x 小的在前

  • 同一个 x 上:

    • 先处理“楼开始”(负高度更小)
    • 再处理“楼结束”(高度为 0)

这样可以保证同一个位置上,先把新楼加进去,再计算高度变化,避免边界处理出锅。

用堆维护“当前最高楼”

我们用一个堆 heap 来维护“当前覆盖这个 x 的所有楼”:

  • 堆的元素是 (neg_h, r):

    • neg_h:负高度
    • r:这栋楼的右边界,用来判断它啥时候过期

遍历事件时,逻辑大概是:

  1. 先把已经“过期”的楼清掉: 只要堆顶的 r <= 当前 x,说明这栋楼已经不覆盖当前 x 了,弹出
  2. 如果当前事件是“楼开始”(neg_h != 0),把 (neg_h, R) 加进堆
  3. 看一眼堆顶,此刻最高高度是 curr_h = -heap[0][0]
  4. 如果 curr_h 和上一个高度 prev_h 不一样,说明天际线发生变化,记录一个点 [x, curr_h]

整体时间复杂度大概是:O(n log n)

  • 排序 O(n log n)
  • 每栋楼进堆出堆一次,也是 O(n log n)

Python 代码实现一遍

直接给你一个函数版本,输入是楼的列表,输出是天际线关键点:

import heapq
from typing import List

defgetSkyline(buildings: List[List[int]]) -> List[List[int]]:
    events = []
for L, R, H in buildings:
# 楼开始事件:高度取负保证大楼优先
        events.append((L, -H, R))
# 楼结束事件:高度为 0,只用 x 触发清理
        events.append((R, 0, 0))

# 按 x 排序,同 x 时,楼开始(-H) 会排在楼结束(0)前面
    events.sort()

# 堆里放 (neg_h, R),初始放一个地面高度 0
    heap = [(0, float('inf'))]
    prev_h = 0
    res = []

for x, neg_h, R in events:
# 先把已经结束的楼从堆里清掉
while heap and heap[0][1] <= x:
            heapq.heappop(heap)

# 遇到楼开始事件,加入堆
if neg_h != 0:
            heapq.heappush(heap, (neg_h, R))

# 当前最高高度
        curr_h = -heap[0][0]

# 如果高度变了,就记录一个关键点
if curr_h != prev_h:
            res.append([x, curr_h])
            prev_h = curr_h

return res

你可以简单测一下,比如:

print(getSkyline([
    [2, 9, 10],
    [3, 7, 15],
    [5, 12, 12],
    [15, 20, 10],
    [19, 24, 8]
]))

会得到一串 [x, h] 的点,把这个点列表画成折线,就是那条“城市天际线”。

这个题看上去是几何题,实际上是“扫描线 + 最大堆 + 精细排序规则”的综合练习,重点就是:

  • 只在“事件点”处理高度变化
  • 用堆维护当前最高楼
  • 注意结束楼的“过期清理”和同 x 排序细节

搞懂这一套,后面遇到矩形覆盖、区间合并、最大区间之类的题,思路会顺很多。

-END-

我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html

🔥虎哥私藏精品🔥

虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》,总量高达650GB。