This article is mainly to help understand how to use stack to solve Leetcode 84 & 85.

P84 Largest Rectangle in Histogram

(DZ) Quick Note: 后大必增，后小则比； 用栈记录谷底，由于高度取决于最低值，长度取决于谷底间距，如遇后谷低则将高度换予前谷；最终回首清栈。

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
class Solution 
{
  public:
    int largestRectangleArea(vector<int>& heights);
};

int Solution::largestRectangleArea(vector<int>& heights)
{
  int res = 0;
  stack<pair<int, int>> s;
  
  for (int i = 0; i < heights.size(); i++)
  {
    int index = i;
    while (!s.empty() && s.top().second >= heights[i])
    {
      index = s.top().first;
      res = max(res, (i - index) * s.top().second);
      s.pop();
    }
    s.push({index, heights[i]});
  }
  
  while (!s.empty())
  {
    res = max(res, (int)(s.top().second * (heights.size() - s.top().first)));
    s.pop();
  }
  return res;
}

P85 Maximal Rectangle

(DZ) Quick Note: 每一行都是P84的子问题，注意height遇零清零。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution 
{
  public:
    int maximalRectangle(vector<vector<char>>& matrix);
    int largestAreaAboveLine(vector<int>& heights);
};

int Solution::maximalRectangle(vector<vector<char>>& matrix)
{
  int res = 0;
  
  if (!matrix.empty())
  {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<int> h(n, 0);
    for (int i = 0; i < m; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (matrix[i][j] == '1')
        {
          h[j]++;
        }
        else
        {
          h[j] = 0;
        }
      }
      res = max(res, largestAreaAboveLine(h));
    }
  }
  return res;
};

int Solution::largestAreaAboveLine(vector<int>& heights)
{
  int res = 0;
  stack<pair<int, int>> s;
  
  for (int i = 0; i < heights.size(); i++)
  {
    int index = i;
    while (!s.empty() && s.top().second >= heights[i])
    {
      index = s.top().first;
      res = max(res, (i - index) * s.top().second);
      s.pop();
    }
    s.push({index, heights[i]});
  }
  
  while (!s.empty())
  {
    res = max(res, (int)(s.top().second * (heights.size() - s.top().first)));
    s.pop();
  }
  return res;
}