leetcode 84. 柱状图中最大的矩形_getlargestarea

leetcode 84. 柱状图中最大的矩形

题目详情

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

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

我的代码

class Solution {
private:
    int res;
public:
    void getLargestArea(vector<int> &heights, int start, int end) {
        if (start == end) {
            res = max(res, heights[start]);
            return;
        }
        int loc = start, loc1 = start;
        for (int i = start; i <= end; ++i) {
            if (heights[i] < heights[loc]) {
                loc = i;
            }
            if (heights[i] > heights[loc1]) {
                loc1 = i;
            }
        }
        int res1 = heights[loc] * (end + 1 - start);
        res = max(res, res1);
        if ((heights[loc1] < res) && ((end + 1 - start) <= res / heights[loc1])) {
            return;
        }
        if (loc == start) {
            getLargestArea(heights, start + 1, end);
            return;
        }
        if (loc == end) {
            getLargestArea(heights, start, end - 1);
            return;
        }
        getLargestArea(heights, start, loc - 1);
        getLargestArea(heights, loc + 1, end);
    }

    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return heights[0];
        }
        res = 0;
        getLargestArea(heights, 0, n - 1);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

我的成绩

执行结果：超出时间限制

一些想法

本道题我的想法是使用递归的方法，每次按范围内的最低点将数组分成三个部分，则最大面积可能在最低点的左边部分出现，也可能在最低点的右边部分出现，还可能出现出现在包含最低点的部分内，然后递归计算。但是卡在了最后一个测试用例上超时了。

执行用时为 0 ms 的范例

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size()==0) return 0;
        if(heights.size()==1) return heights[0];
        int tl;
        vector<int> indexStack; 
        int result;
        int stl;
        int index;

        tl = heights.size();
        result = 0;
        indexStack.push_back(0);
        for(int i=1;i<tl;++i)
        {
            //cout << i << " : " << result << " stack size : " << indexStack.size() << endl;
            if(heights[i] >= heights[indexStack[indexStack.size()-1]])
            {
                indexStack.push_back(i);
                continue;
            }
            while(indexStack.size() > 0 && heights[i] < heights[indexStack[indexStack.size()-1]] )
            {
                stl = indexStack.size();
                if(stl==1)
                {
                    index = indexStack[0];
                    if(heights[index]*i > result)
                        result = heights[index]*i;
                    indexStack.pop_back();
                    break;
                }
                index = indexStack[stl-1];
                if(heights[index]*(i-indexStack[stl-2]-1) > result)
                    result = heights[index]*(i-indexStack[stl-2]-1);
                indexStack.pop_back();
            }
            indexStack.push_back(i);            
        }
        
        while(indexStack.size()>1)
        {
            stl = indexStack.size();
            index = indexStack[stl-1];
            if(heights[index]*(tl-indexStack[stl-2]-1) > result)
                result = heights[index]*(tl-indexStack[stl-2]-1);
            indexStack.pop_back();
        }
        index = indexStack[0];
        if(heights[index]*tl > result)
            result = heights[index]*tl;
        indexStack.pop_back();
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

思考

请参考官方解答。