柱状图下矩形的最大面积LargestRectangleArea

题目

Largest Rectangle in Historgram. 给你一组从左至右排列的柱子的高度，其中每个柱子宽1并且紧靠，要求算出这群柱子下面最大的矩形面积。
比如给你 [2,1,5,6,2,3]， 最大面积由高为5和6的两个柱子组成=10。
Vespa 同学说的这段话非常有道理

每次想算法题，我的基本思路就是，首先先想最直观的解法，不行，就再想分治或者动规这种，再不行，就从数据结构下手！其实这类算法题，根据我的经验，你只要有意识去想分治的思想，如果分治解法存在，那么你总可以想到这个解法的。

暴力法

暴力法是一切的基础，咳咳。
我们可以找以每个柱子为最小高度可以获得的最大面积，所有柱子中最大的最大面积就是答案。
O(n^2)用两层循环，在内循环中每次从a[i]开始向左向右扩张，直到遇到第一个比a[i]小的数a[j],作为边界。这样就可以求得a[i]*n 为最小面积，n是扩张的长度。

分治法

每次找到给定子问题中高度最小的地方。
那么最大面积就是 = max(左边的最大值，amin*length, 右边的最大值)

当然极端情况下会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int largestRectangleArea(int[] height) {
       return largestRect(height, 0, height.length-1);
}
   
   private int largestRect(int[] height, int lo, int hi){
       if (hi-lo <0) return 0;
       int minIdx = minIndex(height,lo,hi);
       int valueM = height[minIdx]*height.length;
       int valueL = largestRect(height, lo, minIdx-1);
       int valueH = largestRect(height, minIdx+1, hi);
       return valueH > valueL? Math.max(valueH, valueM): 
           Math.max(valueL, valueM);
   }
   
   private int minIndex(int[] height, int lo, int hi){
       if (hi-lo <1) return lo;
       int index, i;
       for (i =lo+1, index = lo; i <= hi; i++){
           if (height[i] < height[index])
               index = i;
       }
       return index;
   }

堆栈法

需要我们回过头来审视暴力法，其实我们每次只需要找到a[i]的左右边界即可。而在暴力法的内循环中其实我们已经做了一些a[i]之间的大小比较，而这些信息对于我们之后寻找边界是很有用的。

使用堆栈法，我们维持一个单调非减的堆栈，当a[i] >= a[top] 我们加入堆栈。

当a[i] < a[top]的时候我们找到了以a[top]为最小值的右界i-1。那么以a[top]为最小值的左界在哪呢？答案是栈中 a[top] 下面那个+1，因为a[top]下面那个是第一个小于a[top]的。那么我们就可以把 top 给 pop 出来，依据其左右边界算出以a[top]为最小高度能获得的最大矩形面积。

针对新的a[top]我们重复以上过程直到 a[i] >= a[top] ，a[i]入栈 。

我们看个栗子，以max_list表示记录每个位置的max_area。
a = [2,3,3,4,2,4,1]。//我们人为的再最后加个0，方便最后所有的出栈。

  1. i = 0，a[0]入栈，stack = [0]。
  2. i = 1，a[1]入栈，stack = [0, 1]。
  3. i = 2，a[2]入栈，stack = [0, 1, 2]。
  4. i = 3，a[3]入栈，stack = [0, 1, 2, 3]。
  5. i = 4，此时a[4] < a[top] = 3。
    1. pop a[3]，max_list[3] = 4* (3-(2+1)+1) = 4
    2. pop a[2]，max_list[2] = 3* (3-(1+1)+1) = 6 //注意这里top前一个也是3我们将他也看做是左界。
    3. pop a[1]，max_list[1] = 3* (3-(0+1)+1) = 9
    4. a[4] 入栈，stack = [0, 4]。
  6. i = 5，a[5]入栈，stack = [0, 4, 5]
  7. i = 6，此时a[6] < a[top] = 4。
    1. pop a[5]，max_list[5] = 4* (5-(4+1)+1) = 4
    2. pop a[4]，max_list[4] = 2* (5-(0+1)+1) = 10 //注意这里top前一个也是2我们将他也看做是左界。
    3. pop a[0]，max_list[0] = 2* (5-0+1) = 12 // 此时栈已空，所以左界为0。
    4. a[6] 入栈，stack = [6]。
  8. i = 7，此时a[7] < a[top] = 1。//a[7] = 0
    1. pop a[7]，max_list[7] = 1* (6-0+1) = 7 // 此时栈已空，所以左界为0。

所以最大值是max_list[0] = 12。注意到我们利用的最重要的性质是，栈中top 下面那个一定是第一个左边<=a[top]的位置(有大于的肯定早就被弄出来了)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int largestRectangleArea(int[] height) {
    
    Stack<Integer> s = new Stack<>();
    int maxArea = 0, l;
    for (int i = 0; i <= height.length; i++){
        while (!s.empty() && (i == height.length || 
            height[i] < height[s.peek()])){
            int top = s.pop();
            if (s.empty())
                l = 0;
            else 
                l = s.peek()+1;
            maxArea = Math.max(maxArea, (i-l)*height[top]);
        }
        s.push(i);
    }
    return maxArea;
}

评论