【leetcode】【剑指offer Ⅱ】039. 直方图最大矩形面积

问题描述：

• 给定非负整数数组 heights，数组中的数字用来表示柱状图中各个柱子的高度。
  • 每个柱子彼此相邻，且宽度为 1。
  • 求在该柱状图中，能够勾勒出来的矩形的最大面积。
• 例子如下：
  

核心思路：

• 该题非常经典，值得多做几次，解题方法有很多：双指针暴力解法、分治解法、单调栈解法。
• 双指针暴力解法时间复杂度为 O(n^2)，自然也最容易理解：
  • 在当前柱子下，初始化两个指针分别向左和向右移动，找到左右两边第一个柱子低于当前柱子，即可找到当前高度下可以获得的最大矩形面积。【注意这里相当于固定高度去确定宽度，同理也可固定宽度去确定高度】
  • 暴力法会超时，但是可以通过剪枝去掉一些情况，具体看下面代码实现，粘贴自原题评论区。
• 分治解法平均时间复杂度为 O(nlogn)，对于该题来说分治解法也会超时，但是也值得理解，以下分析来自网友题解（图也来自该网友），这段讲解得很好，我懒得再自己整理了：

  • 以 [2, 1, 5, 6, 2, 3] 为例，可以发现最短的矩形高度 1 的下标为 1，那么最大面积矩形存在三种可能：

    • 第一种可能是该最大矩阵通过最低高度，宽度为数组长度 6（图中绿色部分）；
    • 另一种是矩形完全落在最矮矩阵的左边（即图中标记的 left 部分）；
    • 另一种是矩形完全落在最矮矩阵的右边（即图中标记的 right 部分）。
      

  • 如图所示，确定数组的左右边界，便可以递归进入左边子数组和右边子数组了。

• 单调栈解法是该题的标准答案，时间复杂度为 O(n)，并且单调栈解法还存在普通方法和优化方法。
  • 对于该题，不进行预处理直接使用单调栈思路是可以解决的，前面双指针暴力解法中提及了，指针移动是为了找到当前柱子的下一个更小值，这就是单调栈最直观解决的问题：找到数组中下一个更大或更小的数；因此可以两次反方向遍历确定数组中每一个柱子左边更小值和右边更小值，利用这两个位置可以确定矩形面积的最大值。【要求下一个更小值，所以需要维护栈中是单调递增的】
  • 但是到了这里，该题的解法仍然可以进行优化：只进行一次遍历就可以确定数组中每个柱子的左右更小值。
  • 这个优化基于一个事实：单调栈解法其实是分为从前往后遍历模板和从后往前遍历模板两种的（具体看剑指 offer Ⅱ 038 中的两种解法）；因此当我们在普通解法中从前往后遍历确定下一个更小值的同时，便可以确定前一个更小值（这么讲可能很抽象，可以从具体例子理解）：
    • 以前面的 num = [2, 1, 5, 6, 2, 3] 为例子，假设维护一个栈，栈中存放索引，索引对应的元素单调递增；
    • 当访问到倒数第二个元素 num[4] = 2 的时候，栈中元素为 stk = [0, 2, 3]；
    • 此时 stk.top() = 3，且 2 < num[stk.top()]，所以需要弹出栈顶，弹出前用临时值保存 tmp = stk.top() = 3；
    • 弹出后，此时栈中元素为 stk = [0, 2]，且 num[tmp = 3] = 6、num[4] = 2，则可以确定 6 的下一个更小值为 2，同时可以确定 6 的前一个更小值为 num[stk.top()=2] = 2；【从这里已经看出，单次遍历就可以找到前后更小值位置】
  • 到了这里，只剩下最后一个优化了：在进入单调栈算法前，于原数组 num 尾部插入一个数值 0，这样就保证了单调栈一次遍历结束后栈中不再存在元素（因为题目中提及，数组中只存在非负整数，所以当遇到这个 0 的时候，栈中所有元素都会被清空）；该优化只是为了简化代码，并没有优化时间复杂度。

代码实现：

• 双指针暴力解法如下：【经过优化后，暴力法可通过，代码贴自原题评论区，原为 Java 代码】

  class Solution
  {
  public:
      int largestRectangleArea(vector<int>& heights)
      {
          int max = 0;
          int left = 0;
          int right = 0;
          int m = heights.size();
          for(int i =0;i<m;i++){
              left = i-1;
              right = i+1;
              if(m * heights[i]>max){ // 关键在于此步判断
                  while(left>=0 && heights[left]>=heights[i]){
                      left--; 
                  }
                  while(right<=m-1 && heights[right]>=heights[i]){
                      right++;
                  }
                  max = ::max(max,(right - left - 1)*heights[i]);
              }
          }
          return max;
      }
  };
  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

• 分治解法可以参考下面给出的链接。
• 单调栈普通解法（两次遍历）代码实现如下：【贴自官方题解】

  class Solution {
  public:
      int largestRectangleArea(vector<int>& heights) {
          int n = heights.size();
          vector<int> left(n), right(n);
          
          stack<int> mono_stack;
          for (int i = 0; i < n; ++i) {
              while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                  mono_stack.pop();
              }
              left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
              mono_stack.push(i);
          }
  
          mono_stack = stack<int>();
          for (int i = n - 1; i >= 0; --i) {
              while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                  mono_stack.pop();
              }
              right[i] = (mono_stack.empty() ? n : mono_stack.top());
              mono_stack.push(i);
          }
          
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
          }
          return ans;
      }
  };
  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

• 单调栈优化解法（单次遍历）代码实现如下：

  class Solution
  {
  public:
      int largestRectangleArea(vector<int>& heights)
      {
          heights.emplace_back(0);// 加哨兵
          stack<int> stk;
  
          int ret = 0;
          for(int i = 0; i < heights.size(); ++i)
          {
              while(!stk.empty() && heights[i] < heights[stk.top()])
              {
                  int height = heights[stk.top()];
                  stk.pop();
                  ret = max(ret, height * (stk.empty() ? i : (i - stk.top() - 1)));
              }
              stk.push(i);
          }
          return ret;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22

参考内容：

• 分治解法思路