Skip to content

Hanging Line Method

Introduction

The hanging line method is applicable to a subset of monotonic stack problems. Specifically, the hanging line method can be applied to problems that satisfy the following conditions:

  • Require scanning a sequence while maintaining monotonic information;
  • Can be solved using a monotonic stack;
  • Do not require binary search on the monotonic stack.

It may seem that the hanging line method is replaceable and of little use, but the concept of the hanging line method is simpler than that of the monotonic stack, making it more suitable for beginners in competitive programming to understand and solve problems like the largest submatrix.

Example Problems

SPOJ HISTOGRA - Largest Rectangle in a Histogram

Summary: On a horizontal line, there are \(n\) rectangles each of width \(1\). Find the maximum area of a rectangle that can be inscribed within these rectangles.

A hanging line is a vertical line with two properties: an initial position and a height. It can move left or right as long as its upper endpoint does not exceed the height of the rectangle at the current position.

For a hanging line, we move it left and right as far as possible while keeping its upper endpoint no higher than the current rectangle's height and without moving out of bounds. The area swept by this hanging line is the largest possible rectangle that contains this hanging line. It is easy to see that the largest inscribed rectangle must contain a hanging line with initial position \(i\) and height \(h_i\). Enumerating all such hanging lines and computing the maximum area would take \(O(n^2)\) time, but we can optimize it to \(O(n)\) using the hanging line method.

We consider how to quickly find the leftmost position a hanging line can reach.

Process

Define \(l_i\) as the leftmost position that the hanging line at position \(i\) can extend to. Initially, \(l_i = i\). We need to check whether it can extend further left.

  • If \(l_i = 1\), it has already reached the boundary and cannot extend further.
  • If \(a_i > a_{l_i - 1}\), then the hanging line cannot extend left past position \(l_i - 1\).
  • If \(a_i \le a_{l_i - 1}\), then the hanging line can extend further left. Moreover, the hanging line at position \(l_i - 1\) can extend left to \(l_{l_i - 1}\), so the hanging line at \(i\) can also extend to at least that position. Thus, we update \(l_i\) to \(l_{l_i - 1}\) and continue checking.

Through amortized analysis, it can be proven that each \(l_i\) will be visited by other \(l_j\) at most once, so the time complexity is \(O(n)\).

Implementation

Reference Code 
 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
#include <algorithm>
#include <iostream>
using std::max;
constexpr int N = 100010;
int n, a[N];
int l[N], r[N];
long long ans;
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n, n) {
    ans = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], l[i] = r[i] = i;
    for (int i = 1; i <= n; i++)
      while (l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1];
    for (int i = n; i >= 1; i--)
      while (r[i] < n && a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1];
    for (int i = 1; i <= n; i++)
      ans = max(ans, (long long)(r[i] - l[i] + 1) * a[i]);
    cout << ans << '\n';
  }
  return 0;
}
UVa1619 Feel Good

For a sequence of length \(n\), find a subarray such that the product of the minimum value in the subarray and the sum of the subarray's elements is maximized. If multiple solutions exist, minimize the length; if still multiple, minimize the left endpoint index.

In this problem, we can consider enumerating the minimum value. For each position \(i\), treat \(a_i\) as the minimum and try to extend left and right as far as possible to find an interval \([l, r]\) such that \(\min\limits _ {j = l} ^ r a_j = a_i\). This transforms the problem into the hanging line model.

Reference Code 
 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
#include <cstring>
#include <iostream>
constexpr int N = 100010;
int n, a[N], l[N], r[N];
long long sum[N];
long long ans;
int ansl, ansr;
bool fir = true;
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n) {
    memset(a, -1, sizeof(a));
    if (!fir)
      cout << '\n';
    else
      fir = false;
    ans = 0;
    ansl = ansr = 1;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      sum[i] = sum[i - 1] + a[i];
      l[i] = r[i] = i;
    }
    for (int i = 1; i <= n; i++)
      while (a[l[i] - 1] >= a[i]) l[i] = l[l[i] - 1];
    for (int i = n; i >= 1; i--)
      while (a[r[i] + 1] >= a[i]) r[i] = r[r[i] + 1];
    for (int i = 1; i <= n; i++) {
      long long x = a[i] * (sum[r[i]] - sum[l[i] - 1]);
      if (ans < x || (ans == x && ansr - ansl > r[i] - l[i]))
        ans = x, ansl = l[i], ansr = r[i];
    }
    cout << ans << '\n' << ansl << ' ' << ansr << '\n';
  }
  return 0;
}

Largest Submatrix

P4147 Cow Palace

Given an \(n \times m\) matrix containing 'F' and 'R', find the area of the largest submatrix (area \(\times 3\)) such that every cell in the submatrix is 'F'.

We notice that this problem is very similar to the first one. Upon careful analysis, if we consider each row independently and treat the maximum upward extension of each cell \((x, y)\) as the hanging line length at that position, then the largest submatrix must be one of the largest rectangles obtained by extending these hanging lines left and right.

Reference Code 
 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
#include <algorithm>
#include <iostream>
int m, n, a[1010], l[1010], r[1010], ans;
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      l[j] = r[j] = j;
    }
    char s[3];
    for (int j = 1; j <= m; j++) {
      cin >> s;
      if (s[0] == 'F')
        a[j]++;
      else if (s[0] == 'R')
        a[j] = 0;
    }
    for (int j = 1; j <= m; j++)
      while (l[j] != 1 && a[l[j] - 1] >= a[j]) l[j] = l[l[j] - 1];
    for (int j = m; j >= 1; j--)
      while (r[j] != m && a[r[j] + 1] >= a[j]) r[j] = r[r[j] + 1];
    for (int j = 1; j <= m; j++) ans = std::max(ans, (r[j] - l[j] + 1) * a[j]);
  }
  cout << ans * 3;
  return 0;
}

Practice Problems

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用