TikTok 面试真题解析：柱状图最大矩形面积（Largest Rectangle in Histogram）｜单调栈高频题

TikTok Interview Question: Largest Rectangle in Histogram

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input:
heights = [2,1,5,6,2,3]Output:
10

这道题的目标是在柱状图中找到面积最大的矩形。暴力枚举区间会导致较高的时间复杂度，因此更优思路是：对每个柱子，找到它向左右延伸时第一个比它矮的位置，从而确定以它为最矮高度时能形成的最大宽度。通常使用单调栈来在线性时间内完成左右边界的查找，是这道题的核心技巧。