Leetcode 84

描述

思路

单调栈的思路是如下图的例子
维持一个单调递增的栈，当新的元素（当前元素）大于栈顶元素的时候，就说明以栈顶元素为长的长方形，其宽度最多可以达到当前元素前一个位置。这样子看就可以理解下面的代码了。

代码

class Solution 
{
    public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        stk.push(-1);
        int max_area = 0;
        for (size_t i = 0; i < heights.size(); i++) {
            while (stk.top() != -1 and heights[stk.top()] >= heights[i]) {
                int current_height = heights[stk.top()];
                stk.pop();
                int current_width = i - stk.top() - 1;
                max_area = max(max_area, current_height * current_width);
            }
            stk.push(i);
        }
        while (stk.top() != -1) {
            int current_height = heights[stk.top()];
            stk.pop();
            int current_width = heights.size() - stk.top() - 1;
            max_area = max(max_area, current_height * current_width);
        }
        return max_area;
    }
    // int largestRectangleArea(vector<int>& heights) 
    // {
    //     // use deque, store index of heights
    //     // the elements of deque is monothly increasing, front is the smallest and back is the largest
    //     list<pair<int, int>> m_deque;
    //     int res = heights[0];
    //     m_deque.push_back(make_pair(0,0));
    //     for(int i = 1; i < heights.size(); i++)
    //     {
    //         res = max(res, heights[i]);
    //         bool flag = true;
    //         for(auto it : m_deque)
    //         {
    //             int index = it.first;
    //             int pre_index = it.second;
    //             res = max(res, min(heights[i], heights[index]) * (i - pre_index + 1));
    //             if(heights[i] <= heights[index])
    //             {
    //                 flag = false;
    //                 while(m_deque.back().first != index)
    //                 {
    //                     m_deque.pop_back();
    //                 }
    //                 auto back = m_deque.back();
    //                 m_deque.pop_back();
    //                 m_deque.push_back(make_pair(i, back.second));
    //                 break;
    //             }
    //         }
    //         if(flag)
    //         {
    //             m_deque.push_back(make_pair(i, i));
    //         }
    //     }
    //     return res;
    // }
};