leetcode-largest-rectangle-in-histogram

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/largest-rectangle-in-histogram/

　　给你一个数组，数组中每个元素的值都代表了直方图的高度，最后让你求直方图中的最大面积矩形面积值。

题目分析

　　此题是Hard题，我没有想出来O(n)解法，看了一下这个解法比较好理解，有两个辅助数组left和right。left和right数组代表的含义对于某个位置i，能向左和向右伸展到的位置，意思就是说在i这个位置，以nums[i]为高度的矩形面积就是(right[i] - left[i] + 1) * nums[i]。实际在生成left的数组中，对于每个位置i需要进行不断“跳跃”，比如说求left[i]时，初始值是i，那么先看跟i-1位置的值进行比较，如果i-1位置的值更大，那么自然left[i]可以跳跃到left[i-1]的位置，那么再看此时位置-1的位置的值跟nums[i]比较再决定是否继续跳跃。构造right数组也同理，逆向思维即可。

　　这个算法思路比较好，在构造left数组的代码段中:

1
2
3
4
5
6
7
for(int i = 1; i < s; i++) {
  int jump = i;
  while (jump > 0 && nums[jump - 1] >= nums[i]) {
    jump = left[jump - 1];
  }
  left[i] = jump;
}

　　这里看似复杂度是O(n^2)，这里利用了均摊分析的思想，我们可以考虑nums[i+1]和nums[i]的关系，假定i位置已经计算过，该计算i+1，如果nums[i+1]比nums[i]值大，根本不需要跳跃，如果小于nums[i]，那么直接跳到了left[i-1]的位置，也就是说i+1不会再次遍历i曾经跳跃的位置，而是使用了i跳跃到的边界位置作为初始点，因此，从均摊分析角度看，复杂度是O(n)

代码

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> nums = heights;
        int s = heights.size();
        if(s == 0) {
            return 0;
        }
        int ans = 0;
        vector<int> left(s, 0);
        vector<int> right(s, 0);
        //left
        left[0] = 0;
        for(int i = 1; i < s; i++) {
            int jump = i;
            while (jump > 0 && nums[jump - 1] >= nums[i]) {
                jump = left[jump - 1];
            }
            left[i] = jump;
        }
        //right
        right[s - 1] = s - 1;
        for(int i = s - 2; i >= 0; i--) {
            int jump = i;
            while (jump < s - 1 && nums[jump + 1] >= nums[i]) {
                jump = right[jump + 1];
            }
            right[i] = jump;
        }
        
        for(int i = 0; i < s; i++) {
            ans = max(ans, (right[i] - left[i] + 1) * nums[i]);
        }
        return ans;
    }
}

　　复杂度是:O(n)