团子员工爆料：转部门面试通过，被现ld挽留，承诺年底绩效+涨薪，ld是今年年中转岗过来的。。
鬼哥约 4 分钟看到一个网友分享了个挺有意思的事——他在转部门面试通过后，原部门的领导（LD）以“年底绩效+涨薪”为由，试图挽留他。
话说这LD是今年年中才转岗过来的，结果他所在的部门也有点缺人，所以这番话到底有多少可信度呢？
从我的角度来说，这种情况基本上是“信口开河”的几率大于真实承诺。特别是LD本身就是刚转来的，部门又急需人手。
这种“承诺”基本上是没有多少实质性的保障，背后很可能是为了填补部门的空缺，别太把“年底绩效+涨薪”当成一回事，往往等到年底，看看人手再说，自己也就成了“被替代”的一员。
很多时候这类承诺都是空头支票，一旦找到替代者，你就会轻易被“抛弃”了。
所以，不要轻易相信什么“承诺”！有时候，最靠谱的就是做好自己，留一手，别把希望全寄托在领导的嘴上🤷♂️。
算法题：柱状图中最大的矩形
今天我们来聊一个经典的算法问题：柱状图中最大的矩形。这题有点难度，但也很有意思，而且它是各种面试、竞赛中常见的考点，所以咱们程序员得认真攻克一番。
先来解释一下这个题目。假设你有一个柱状图，每个柱子的宽度为 1，高度由一个数组表示。现在，问题就是：你要找出其中能够形成的最大矩形的面积。简单来说，就是从这些柱子中找出一个矩形，要求它的面积最大。
一开始的直觉方法
很多同学看到这个题目，第一个反应可能是暴力破解：遍历每两个柱子之间的所有可能矩形，然后计算它们的面积，最后找到最大的。这种方法直觉上没错，但是时间复杂度可不低，最坏的情况是 (O(n^2))，其中 n 是柱子的数量。对于数据量比较大的时候，这个时间复杂度完全无法接受。
所以，我们得想办法优化一下。
单调栈解法
问题的关键就在于：如何高效地计算每个柱子为底边时，能够组成的最大矩形面积呢？在这儿，我给大家推荐一个非常经典的做法——单调栈。
首先，你要理解栈在这里的作用。我们将柱子的索引按从小到大的顺序（高度）入栈，这样栈顶的柱子总是当前范围内的最低柱子。而当我们遇到一个比栈顶柱子低的柱子时，就意味着当前栈里的柱子不再能与这个新柱子形成更大的矩形。此时我们就得pop出栈顶元素，计算面积，并继续尝试。
来看看代码吧：
public class MaxRectangle {
public int largestRectangleArea(int[] heights) {
// 创建一个栈
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int i = 0; // 遍历柱状图
while (i < heights.length) {
// 如果栈为空，或者当前柱子高度大于栈顶柱子的高度，就入栈
if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
stack.push(i++);
} else {
// 否则，弹出栈顶，计算面积
int height = heights[stack.pop()];
// 计算宽度：如果栈为空，说明栈顶的柱子可以延伸到第0个柱子；
// 否则，它的宽度是当前柱子和栈顶柱子之间的差
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
}
// 处理栈中剩下的柱子
while (!stack.isEmpty()) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
return maxArea;
}
}
代码分析
在这个解法中，我们用一个栈来存放柱子的索引。栈的作用是帮助我们快速找到每个柱子的“左右边界”。当遍历到一个比栈顶元素矮的柱子时，说明以栈顶元素为高的矩形无法继续扩展了，就要计算这个矩形的面积，并更新最大面积。
如果栈为空，说明目前这个柱子可以和前面的所有柱子形成矩形。如果栈非空，说明当前柱子可以延续栈顶柱子的高度，形成新的矩形。
为什么这是 O(n) 的解法？
你可能会问，栈的操作不也是 O(n) 吗？没错，栈的每个元素最多进栈一次，出栈一次，所以整个过程中每个元素最多做两次操作（进栈和出栈），因此这个解法的时间复杂度是 O(n)，比暴力解法要快得多。
测试案例
让我们来试一下一个简单的例子：
public class Main {
public static void main(String[] args) {
MaxRectangle solution = new MaxRectangle();
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println(solution.largestRectangleArea(heights)); // 输出 10
}
}
在这个例子中，柱状图的高度是 [2, 1, 5, 6, 2, 3]。最大的矩形是在柱子高度为 5 和 6 之间形成的，宽度为 2，面积是 10。所以输出应该是 10。
总结
这道题通过使用单调栈的技巧，将复杂度从暴力解法的 (O(n^2)) 降到了 (O(n))，非常高效。栈的使用可以让我们快速计算出每个柱子为底的矩形面积，同时确保我们始终保持高效的时间复杂度。这也是很多面试官考察的一个经典算法，掌握它对提高编程能力非常有帮助。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。