leetcode84：柱状图中最大的矩形

题目链接

leetcode

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

/*
    单调栈
    
    枚举「高」，某一个柱子的高度为 h，向左右两边扩展，使柱子的高度均不小于 h。
    找到左右两侧最近的高度小于 h 的柱子，这两个柱子之间所有柱子高度均不小于 h。

    时间复杂度：O(n)
        遍历数组，对栈的操作的次数为 O(n)。
    空间复杂度：O(n)
        栈的大小为 O(n)。
*/
class Solution_2 {
public:
    int largestRectangleArea(vector<int>& heights_cases) {
        int n = heights_cases.size();
        vector<int> left(n), right(n);

        stack<int> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && heights_cases[stk.top()] >= heights_cases[i]) {
                stk.pop();
            }
            if (stk.empty()) {
                left[i] = -1;
            } else {
                left[i] = stk.top();
            }
            stk.push(i);
        }

        stk = stack<int>();
        for (int i = n-1; i >= 0; i--) {
            while (!stk.empty() && heights_cases[stk.top()] >= heights_cases[i]) {
                stk.pop();
            }
            if (stk.empty()) {
                right[i] = n;
            } else {
                right[i] = stk.top();
            }
            stk.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = max(res, (right[i]-left[i]-1) * heights_cases[i]);
        }
        return res;
    }
};

/*
    单调栈

    栈中元素从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
    本题单调栈的顺序，正好与接雨水反过来。
    栈顶和栈顶的下一个元素以及要入栈的三个元素，组成了最大面积的高度和宽度。

    时间复杂度：O(n)
        每个元素最多进栈一次，出栈一次。
    空间复杂度：O(n)
        存储栈的空间 O(n)。
*/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights_cases) {
        int result = 0;
        stack<int> stk;
        heights_cases.insert(heights_cases.begin(), 0); // 数组头部加入元素0
        heights_cases.push_back(0); // 数组尾部加入元素0
        stk.push(0);
        
        // 第一个元素已经入栈，从下标1开始
        for (int i = 1; i < heights_cases.size(); i++) {
            while (!stk.empty() && heights_cases[i] < heights_cases[stk.top()]) {
                int mid = stk.top(); stk.pop();

                if (!stk.empty()) {
                    int left = stk.top();
                    int right = i;
                    int w = right-left-1;
                    int h = heights_cases[mid];
                    result = max(result, w*h);
                }
            }
            stk.push(i);
        }

        return result;
    }
};

// 辅助函数：打印数组
void printArray(vector<int>& nums) {
	cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size()-1) {
            cout << ",";
        }
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> heights_cases = {
        {2,1,5,6,2,3},
        {2,4}
    };

    for (int i = 0; i < heights_cases.size(); i++) {
        auto& heights = heights_cases[i];

        cout << "Input: heights = ";
        printArray(heights);
        cout << endl;
        int result = solution.largestRectangleArea(heights);
        cout << "Output: " << result << endl;
    }
    
    return 0;
}