最近看到一个网友的吐槽。他说自己失业两个月了，找工作找得快疯了，去面试了Java研发的岗位，连外包的offer都接不到，结果居然收到了外企技术经理的offer。
这不禁让我想起了自己之前的求职经历。我也曾经历过“外包offer难接”的痛苦时期。当时感觉自己无论怎么努力都看不到希望，外面看似有很多机会，然而大多数都只是外包公司的低级岗位和不太感兴趣的项目。
可是，有时候真的是命运捉弄人。
像这个网友一样，就因为某个契机被看上，反倒是获得了一个意想不到的机会。
所以这个世界上很多东西，都不是努力就能换来的，有时你得碰上一个对的时机，一个对的人，一个对的机会。
算法题：柱状图中最大的矩形
一个在面试中出现频率挺高的经典算法题：柱状图中最大的矩形。不知道大家有没有碰到过这道题，反正我每次刷 LeetCode 和面试时，这道题都能给我带来不少“惊喜”！😅
这道题的意思其实很简单：给定一个柱状图，每个柱子的高度不同，求出图中可以形成的最大的矩形面积。看似简单，实际的挑战点在于如何快速找到最大矩形的面积，而不是暴力破解。简单来说，如果你不使用聪明的算法，可能会遍历一次图的每个柱子，这样做的时间复杂度是 O(n²)，效率显然是不够高的。
暴力解法：O(n²)的方式
最直接的办法是，遍历每一对柱子，然后计算它们之间能组成的矩形的面积，最后找出最大的矩形。其实想法是对的，但是复杂度高得惊人。我们可以写个简单的 Python 示例代码来看看：
def largestRectangleArea(heights):
n = len(heights)
max_area = 0
for i in range(n):
for j in range(i, n):
min_height = min(heights[i:j+1]) # 找到当前子区间的最小高度
area = min_height * (j - i + 1) # 计算矩形面积
max_area = max(max_area, area)
return max_area
# 示例
heights = [2, 1, 5, 6, 2, 3]
print(largestRectangleArea(heights)) # 输出 10
看上去确实能解决问题，但这种暴力破解的方式，时间复杂度是 O(n²)，对于大规模数据时简直是灾难。想想如果数据有百万级别，程序可能就得等到老天爷来救了（当然是等待超时）。😩
优化解法：单调栈，O(n)的方式
幸好，暴力解法的效率是可以优化的。我们可以使用一个单调栈来解决这个问题，这种方法的时间复杂度可以优化到 O(n)，非常高效！
单调栈的核心思想是通过栈来保持一个递增的顺序。当我们遇到一个柱子的高度比栈顶的柱子低时，就可以利用栈中已经存储的柱子来计算可能的矩形面积。可以说，单调栈是这类问题的神器，能让你在 O(n) 内搞定。
代码实现如下：
def largestRectangleArea(heights):
heights.append(0) # 加一个0，确保栈中的所有柱子能被弹出
stack = [-1] # 用一个栈来存储柱子索引
max_area = 0
for i in range(len(heights)):
# 当当前柱子小于栈顶柱子时，弹出栈顶并计算面积
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1 # 计算宽度
max_area = max(max_area, h * w)
stack.append(i) # 将当前柱子索引入栈
return max_area
# 示例
heights = [2, 1, 5, 6, 2, 3]
print(largestRectangleArea(heights)) # 输出 10
这段代码的逻辑其实是这样的：我们从左到右遍历柱子，如果当前柱子的高度大于栈顶的柱子，就把它入栈；如果当前柱子的高度小于栈顶的柱子，就从栈里弹出柱子，计算形成的矩形面积，并更新最大面积。直到所有柱子都遍历完，栈里剩下的就是所有可能的矩形面积。
通过这种优化，我们将时间复杂度降到了 O(n)，大大提高了程序效率。
重点细节解析
加一个0的巧妙技巧：为了确保最后栈里的所有柱子都能被处理完，我们在 heights 列表末尾加上一个 0。这就能保证栈中的所有柱子都会被弹出并计算面积。
单调栈的特点：栈中的元素是按从小到大的顺序排列的。每次遇到比栈顶元素小的柱子时，我们就可以计算出以栈顶元素为高度的最大矩形面积。这是核心技巧，也是算法的精髓所在。
总结
这道柱状图中最大的矩形题目，不仅考察了算法的设计能力，还能让你深入理解栈这一数据结构的应用。暴力解法虽然能工作，但显然不够高效。而单调栈的解法，不仅高效且简洁，能轻松应对大规模数据。通过这些优化技巧，我们能够以 O(n) 的时间复杂度解决这个问题。
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。
