LC stack

  1. 84. Largest Rectangle in Histogram

    detail explain

    简单来讲,建立stack并由左往右遍历数组。若新遇到的比stack最后一个元素小,则说明新遇到的元素 R 作为右边界,stack中第一个比该元素小的元素作为左边界(不包含),可以构建一个高度为 R 的当前可找到的最大面积。由于继续向右时比 R 高的都会被 R 限制,所以stack中比R大的元素可以全部pop出来了。至此,我们可以找到任何元素与其左手边的元素构造的最大面积。

    之后我们只需再找所有stack中元素与右手边元素构造的最大面积即可。由于stack最终必定是递增的,也就意味着stack最后一个元素一直到原本直方图的尾巴这段中都比stack最后一个元素要大。所以只需要每次pop最后一个元素,并以其高度乘以其位置到末尾的距离来计算面积,由此即可得到与其右手边的元素构造的最大面积。

发表评论

电子邮件地址不会被公开。 必填项已用*标注