LeetCode 84. Largest Rectangle i

题目描述

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，求最大的长方形面积。

1. 对于每一个bar，去找右侧若干个包括自身最大的。
   从左到右遍历，左边比右边大时停止，计算。

2. 对每一个bar去找从这个bar位置往左和往右第一个小于此bar的索引，记ln为左边索引，rn为右边索引，最后结果是
   (rn - ln - 1) * height[bar]。

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int i, j;
        int max, value = 0;
        for (i = 0; i < heights.size() - 1; i++)
        {
            for (j = i + 1; j < heights.size(); j++)
            {
                if (heights[i] <= heights[j])
                {
                    if (j == heights.size() - 1)
                    {
                        max = (j - i + 1) * heights[i];
                        if (max > value)
                        {
                            value = max;
                        }
                    }
                }
                else if (heights[i] > heights[j])
                {
                    if (j == i + 1)
                        max = (j - i + 1) * heights[j];
                    else if (j > i + 1)
                        max = (j - i) * heights[i];
                    if (max > value)
                    {
                        value = max;
                    }
                    break;
                }
            }
        }
        return value;
    }
};

时间复杂度

O(n^2)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> s;//记录当前非递减队列的索引
        heights.push_back(0);//增加一个0
        int value = 0;
        int sum = 0;
        int i = 0;
        while (i < heights.size())
        {
            if (s.empty() || heights[i] > heights[s.back()])//s为空或者当前的大于栈顶的
            {
                s.push_back(i);
                i++;
            }
            else//当前的小于栈顶的
            {
                int t = s.back();//栈顶的索引
                s.pop_back();
                if (s.empty())//s为空
                {
                    value = heights[t] * i;
                }
                else
                    value = heights[t] * (i - s.back() - 1);
                    //i是当前bar往右数的第一个小于当前bar的索引
                    //s.back()是往左数的第一个小于bar的索引
                if (value > sum)
                    sum = value;
            }
        }
        return sum;
    }
};