Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Hard 84. Largest Rectangle in Histogram

leetcode
tags: leetcode

問題

幅が$1$のヒストグラムのバーの高さを表した非負整数が$n$個与えられたとき, ヒストグラムの最も広い長方形の領域を見つけろ

解法(recursive)

まずはナイーブに考えます

そうすると長方形の左端と右端の組み合わせを全て考える, その中で最小のバーを探すので時間計算量が$O(n^{3})$となります

これは流石に通らないのでもう少し計算量を改善させます

Divide & Conquer

日本語だと分割統治法です. 問題を小さな問題に分割してそれを解く方法です

今回は左端から伸びる長方形と右端から伸びる長方形と真ん中と横切る長方形に問題を分けます

  • 左側と真ん中と右側に分ける関数を用意します
  • 得られた左側, 真ん中, 右側のうち最大の面積を返します
  • 真ん中の最大を取る関数のみを実装します
    • これによって再帰的に左側と右側の面積も求められます
  • 真ん中の最大の面積を求める関数は以下のように実装します
    • 中心を区間左端left, 中心の次の場所を区間右端rightとします
    • 高さをその区間内で最も低い高さとします
    • そして, 底辺の長さはright - left + 1です
    • この区間左端と区間右端が中央の右端と左端を超えるまでずらしていきます

計算量

与えられる配列の長さを$n$とします

  • 空間計算量
    • 再帰の深さに応じて空間計算量を使うので$O(\log(n))$です
  • 時間計算量
    • 再帰関数は$O(\log(n))$回実行されます
    • 中央の区間の最大の要素を求めるのは$O(n)$です
    • それらをかけ合わせて全体で$O(n \log(n))$

Python

class Solution:
  def largestRectangleArea(self, heights: List[int]) -> int:
    if not heights:
      return 0
    return self.max_area(heights, 0, len(heights) - 1)
  
  def max_combine_area(self, heights, start, mid, end):
    left, right, area = mid, mid+1, 0
    h = min(heights[left], heights[right])
    while start <= left and right <= end:
      h = min(h, min(heights[left], heights[right]))
      area = max(area, (right - left + 1) * h)
      if left == start:
        right += 1
      elif right == end:
        left -= 1
      else:
        if heights[left - 1] > heights[right + 1]:
          left -= 1
        else:
          right += 1
    return area
    
  def max_area(self, heights, start, end):
    if start == end:
      return heights[start]
    mid = start + (end - start) // 2
    left_area, right_area, middle_area = self.max_area(heights, start, mid), self.max_area(heights, mid+1, end), self.max_combine_area(heights, start, mid, end)
    return max(left_area, right_area, middle_area)

C++

class Solution {
public:
  int largestRectangleArea(vector<int>& heights) {
    if (heights.empty()) {
      return 0;
    }
    return maxArea(heights, 0, heights.size() - 1);
  }
  
private:
  int maxCombineArea(const vector<int>& heights, int start, int mid, int end) {
    int left = mid, right = mid+1;
    int area = 0, h = min(heights[left], heights[right]);
    while (start <= left && right <= end) {
      h = min(h, min(heights[left], heights[right]));
      area = max(area, (right - left + 1) * h);
      if (left == start) {
        ++right;
      } else if (right == end) {
        --left;
      } else {
        if (heights[left-1] > heights[right+1]) {
          --left;
        } else {
          ++right;
        }
      }
    }
    return area;
  }
  
  int maxArea(const vector<int>& heights, int start, int end) {
    if (start == end) {
      return heights[start];
    }
    int mid = start + (end - start) / 2;
    int leftArea = maxArea(heights, start, mid);
    int rightArea = maxArea(heights, mid+1, end);
    int middleArea = maxCombineArea(heights, start, mid, end);
    return max({leftArea, rightArea, middleArea});
  }
};

ちなみに

他にもStackを用いた解法があるようですがいまいち理解できないので今度出来たらまた解説を書きます