LeetCode 84. Largest Rectangle in Histogram题目解析-wowAC

Description

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.


Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].


The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

题目复述

给定n个非负整数,每个整数代表宽度为1高度为该数的直方图的长条,找出直方图中面积最大的矩形区域。

题目解析

一个很直观的方法是枚举所有长条区间,找出长条中高度最小的数乘以区间宽度就是当前的面积,找出最大面积即可,根据这个思路我们可以考虑如何优化,对于一个长条而言,假设他是区间内最矮的长条,我们需要向左拓展找出第一个比当前高度矮的长条位置,这就是他的左边界,向右拓展,同样找出第一个比当前高度矮的长条位置,这就是他的右边界。对于每个高度,找出对应区间,那么答案就会很自然求出来。如下图所示

image.png

现在问题转化为了如何求一个长条的左边界(左边距离他最近且更矮的长条)和右边界(类似于左边界),对于这个问题可以使用单调栈来求解,什么是单调栈呢?通俗的讲就是往栈内push元素的时候,去除栈顶会破坏栈的单调性的元素。为了求左边界,我们总是要求栈底到栈顶的元素是严格递增的,所有栈顶元素大于等于要push元素的都要pop出来,push前栈顶的数即为当前要push数的左边界。例如对于题目中的样例[2 1 5 6 2 3],单调栈是这样操作的:

stack 表示栈,存储高度的下标,L[]数组,L[i]表示下标为i的长条的左边界。如果栈空,则当前L[i] = -1, -1是一个虚拟位置。

stack={}

L[0]=-1

push(0) => stack={0}

heights[1]<=heights[0] => pop(0) =>stack = {}

stack={}

L[1]=-1

push(1)=>stack={1}

heights[2]>heights[1]不需要pop因为没有破坏单调性

L[2]=1

push(2) => stack={1, 2}

heights[3]>heights[2]不需要pop因为没有破坏单调性

L[3]=2

push(3) => stack={1, 2, 3}

heights[4]<=heights[3] => pop(3) => stack={1, 2}

heights[4]<=heights[2] => pop(2) => stack={1}

heights[4]>heights[1]不需要pop因为没有破坏单调性

L[4]=1

push(4) => stack={1, 4} ……

对于右边界可以用同样的操作方式来求解。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> st; //栈 用于存储下标
        vector<int> L(heights.size());  //L[i]表示i左边距离i最近的heights小于heights[i]的位置
        vector<int> R(heights.size());  //R[i]表示i右边距离i最近的heights小于heights[i]的位置
        for(int i=0; i<heights.size(); i++) {
            while(!st.empty() && heights[st[st.size()-1]]>=heights[i])
                st.pop_back();
            if(st.empty()) L[i] = -1;
            else L[i] = st[st.size()-1];
            st.push_back(i);
        }
        st.clear();
        
        for(int i=heights.size()-1; i>=0; i--) {
            while(!st.empty() && heights[st[st.size()-1]]>=heights[i])
                st.pop_back();
            if(st.empty()) R[i] = heights.size();
            else R[i] = st[st.size()-1];
            st.push_back(i);
        }
        st.clear();
        //求解答案
        int res = 0;  
        for(int i=0; i<heights.size(); i++) {
            res = max(res, heights[i]*(R[i]-(L[i]+1))); //注意宽度的求解
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注