leetcode84 柱状图中最大矩形

题目

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

image.png

示例:

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

分析

这题让我学会了一个经典的算法 -- 单调栈。

步骤

使用栈结构来维护一个单调队列。

1. 当栈为空或者栈顶元素＜=遍历到的元素时，元素下标 i 压入栈顶。
2. 当遍历到<栈顶的元素时，将栈顶元素逐个出栈，计算面积()。直到满足栈顶元素<=遍历到的元素时，将该元素入栈。

代码

class Solution {
public:

    //N*N解法
    // int largestRectangleArea(vector<int>& nums) {

    //     int len = nums.size();
    //     int res = 0, min;

    //     for (int i = 0; i < len; i++){
    //         for (int j = i; j < len; j++){
    //             if (j == i){
    //                 min = nums[j];
    //             }else{
    //                 if (nums[j] < min){
    //                     min = nums[j];
    //                 }
    //             }
    //             res = max(res, min * (j - i + 1));
    //         }
    //     }

    //     return res;
    // }

    //单调栈解法
    int largestRectangleArea(vector<int>& nums) {
        stack<int> stk;
        stk.push(-1);

        int top, cur, res = 0;

        for (int i = 0; i < nums.size(); i++){
            while (stk.top() != -1 && nums[stk.top()] > nums[i]){
                top = nums[stk.top()];
                stk.pop();

                cur = top * (i - stk.top() - 1);

                res = max(res, cur);
            }
            stk.push(i);
        }

        while (stk.top() != -1){
            top = nums[stk.top()];
            stk.pop();

            cur = top * (nums.size() - stk.top() - 1);

            res = max(res, cur);
        }

        return res;
    }                     
};