题目

题目找出柱状图中最大的面积。如下图：

1
2
3
输入：[2,1,5,6,2,3]
最大面积取在5、6之间, 
输出：5*2=10

例子
例子

方法一 超时

直接暴力求解，计算在i～j范围内的最大面积，时间复杂度O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;
        int result = INT_MIN;
        for (int i = 0; i < heights.size(); i++) {
            for (int j = i; j < heights.size(); j++) {
                result = max(result, calArea(heights, i, j));
            }
        }
        return result;
    }
    int calArea(vector<int> &heights, int start, int end) {
        auto min_val = *min_element(heights.begin()+start, heights.begin()+end+1);
        return min_val * (end-start+1);
    }
};

方法二 O(nlogn)

从上面那个方法可以看出，每一块面积取决于最矮的那一个点，因此找到i~j范围内最小的点min_index, 最大面积等于max(Area(i,j), Area(i, min_index-1), Area(min_index+1, j)), 当min_index不平均时，时间复杂度O(n^2)，平均时，时间复杂度O(nlgn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;
        return calArea(heights, 0, heights.size()-1);
    }
    int calArea(vector<int> &heights, int start, int end) {
        if (start > end || start > heights.size()-1 || end < 0) return INT_MIN;
        int min_index = start;
        for (int i = start+1; i <= end; i++) {
            if (heights[i] < heights[min_index]) min_index = i;
        }
        int left = calArea(heights, start, min_index-1);
        int right = calArea(heights, min_index+1, end);
        return max(heights[min_index] * (end-start+1), max(left, right));
    }
};

方法三 O(n)

  • 比如[2,4]这样的序列，面积可选[2*2, 1*4]，此时：
    • 如果4后面的元素大于等于4，则面积至少可选[4*2, 2*3]等。
    • 如果后面的元素小于4，这时可以求面积，因为之后的面积会受限于后面的元素，比如[2,4,3]，其中3小于4，如果3后面的元素是6,[2,4,3,6]中索引0~2的面积是取决于4之前的2。
  • 对于每个元素，找到它：左边比它小的最近元素、右边比它小的最近元素，则可以确定一个面积
  • 维护一个单调递增的栈，每当找到一个山峰(也就是[1,3,2]这种形式)，计算左右边界的面积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;
        int result = 0;
        stack<int> s;
        for (int i = 0; i <= heights.size(); i++) { // i = heights.size()用于处理栈里面只有升序的情况
            if (s.empty() || (i < heights.size() && heights[s.top()] <= heights[i])) {
                s.push(i);
            } else {
                // 遇到右边界时
                int top = s.top();  // 当前最高点
                s.pop();
                int left = s.empty()? -1: s.top(); // 左边界，-1是栈为空时，左边界是0的左边-1
                result = max(result, heights[top] * (i - left - 1));
                i--; // 没有计算heights[i]是最高点时的情况，所以保持i的位置
            }
        }
        return result;
    }
};