[Leetcode]Largest Rectangle in Histogram(C++)

题目描述

例子

例子 1

Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.

例子 2

Input: heights = [2,4] Output: 4

Constraints

1 <= heights.length <= 10^5

0 <= heights[i] <= 10^4

解题思路

可以用一个栈来维护之前遇到的最大高度，来作为是否更新结果的判断标准，遍历所有高度：

栈为空时，直接将当前高度的下标压入栈中，检查下一位置
栈顶元素小于当前高度时，结果不会变（因为还是只能取栈顶元素高度构建长方形），同样压入栈中，检查下一位置
栈顶元素大于当前高度时，意味着之后的 bar 不能利用栈顶高度构建长方形，因此最大结果 有可能更新，因此需要进行更新，方法如下：
- 栈顶取出之前最大高度的下标作为高度
- 用当前下标到下一个栈顶的位置的距离作为宽度（需要减一，因为下一个栈顶的高度有可能比当前高度低，不一定能用）
- 宽 * 高作为当前面积来进行最优值更新
- 重复该操作，直至遇到栈为空或栈顶小于当前高度

代码如下：

#include <stack>
#include <vector>

class Solution {
public:
    int largestRectangleArea(std::vector<int>& heights) {
        // place holder
        heights.push_back(0);
        std::stack<int> stk;
        int result = 0;
        int idx = 0;
        while (idx < heights.size()) {
            // #1 stack empty, push the height to the stack
            // #2 current height higher than the previous highest height
            if (stk.empty() || heights[idx] >= heights[stk.top()]) {
                stk.push(idx++);
            } else {
                // #3 meet a lower bar, the previous highest bar is unuseable,
                // hence remove it from stack, update the result (compare to use
                // current height to the top of stack), keep doing this step,
                // until meet another lower bar
                int h = heights[stk.top()];
                stk.pop();
                int w = stk.empty() ? idx : idx - stk.top() - 1;
                result = std::max(result, h * w);
            }
        }

        return result;
    }
};

时间复杂度: O(n) – 每个元素最多只被遍历两次（压入一次，往回检查一次）
空间复杂度: O(n)

GitHub 代码同步地址： 84.LargestRectangleInHistogram.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions