Keshawn_lu's Blog

Leetcode 84. 柱状图中最大的矩形

栈
字数统计: 662阅读时长: 2 min
2020/05/30 Share

题目简介：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

1
2
输入: [2,1,5,6,2,3]
输出: 10

思路：

首先我们得先知道对于一个矩形，它所能达到的最大面积取决于最短的那条边，所以例如上图高度为5的矩形，它要想达到以5为高度的最大面积，就必须往左右找能大于等于它高度的矩形，这样子以5为高度的矩形才能有最大的宽度。所以我们需要去找右边界与左边界。换个角度想，我们在左右两边只要找到第一个高度比5小的矩形，它们中间的矩形的高度一定都>= 5。

所以问题转换为了往左右两边找第一个比目标矩阵高度小的矩形。这时我们就可以利用栈了。

遇到比栈顶元素大的值，则直接入栈；否则，此时的元素为右边界，可以先记为heights[target]，开始弹出栈顶元素，直到heights[target]比栈顶元素大。

注意每次弹出的栈顶元素都是我们要的目标矩形

每次弹出一个元素时，此时的栈顶元素便是该目标矩形的左边界，即目标矩形左边第一个比它高度小的矩形；右边界我们之前已经知道了，这样子目标矩形的最大面积便为heights[top_index] * (right - left - 1)，遍历时保存最大值，最后返回即可。

tips:

  • 可以在heights数组最后插入一个0，来代表末尾边界。
  • 注意在求左边界时，目标矩形无左边界的情况。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {

        stack<int> st;
        
        if(heights.size() == 0)
            return 0;

        int maxArea = heights[0];

        heights.push_back(0);   //设置末尾边界

        for(int i = 0; i < heights.size(); i++){

            while(!st.empty() && heights[i] < heights[st.top()]){

                int top_index = st.top();

                //右边第一个比heights[st.top()]小的元素
                int right = i;

                st.pop();
                //左边第一个比heights[st.top()]小的元素
                int left = st.empty() ? -1 : st.top();	//注意无左边界的情况

                maxArea = max(maxArea, heights[top_index] * (right - left - 1));
            }

            st.push(i);
        }

        return maxArea;
        
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网