LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 对每一行计算以该行为底边的最大高度

10100    10100
10111    20211
11111 => 31322
10010    40030

• 对每一行按 #84 求解

10100 => 求出高度依次为 10100 的柱状图的最大矩形面积
20211 => 求出高度依次为 20211 的柱状图的最大矩形面积
31322 => 求出高度依次为 31322 的柱状图的最大矩形面积
40030 => 求出高度依次为 40030 的柱状图的最大矩形面积

• 因此只需要求出每一行对应的数组，再复用 #84 的解法即可

class Solution {
 public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    if (empty(matrix)) return 0;
    int res = 0;
    vector<int> dp(size(matrix[0]) + 1);
    for (auto& x : matrix) {
      for (int i = 0; i < size(x); ++i) {
        if (x[i] == '1') {
          ++dp[i];
        } else {
          dp[i] = 0;
        }
      }
      res = max(res, largestRectangleArea(dp));
    }
    return res;
  }

  int largestRectangleArea(const vector<int>& heights) {
    stack<int> s;
    int res = 0;
    for (int i = 0; i < size(heights); ++i) {
      while (!empty(s) && heights[i] < heights[s.top()]) {
        int t = s.top();
        s.pop();
        res = max(res, heights[t] * (empty(s) ? i : (i - s.top() - 1)));
      }
      s.emplace(i);
    }
    return res;
  }
};