1.2.7 Monotonic Stack

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

/*

A monotonic stack maintains its elements in sorted order as values are pushed, popping away any
entries that would violate the ordering. Scanning an array once while keeping such a stack of
indices answers, for every position, where the nearest smaller or larger neighbor lies. These
"nearest smaller/greater" relationships underlie many array problems, the most famous being the
largest rectangle in a histogram. Each index is pushed and popped at most once, so a full scan runs
in linear time.

All functions below take a vector `a` of $n$ comparable values and return a vector of $n$ indices.
A "less" query uses a strictly smaller neighbor and a "greater" query uses a strictly larger one;
changing the comparison from strict to non-strict (e.g. `>=` to `>`) toggles how ties are handled.

- `previous_less(a)` returns, for each $i$, the largest index $j < i$ with $a[j] < a[i]$, or $-1$ if
  there's no such index.
- `next_less(a)` returns, for each $i$, the smallest index $j > i$ with $a[j] < a[i]$, or $n$ if
  there's no such index.
- `previous_greater(a)` returns, for each $i$, the largest index $j < i$ with $a[j] > a[i]$, or $-1$
  if there's no such index.
- `next_greater(a)` returns, for each $i$, the smallest index $j > i$ with $a[j] > a[i]$, or $n$ if
  there's no such index.
- `largest_rectangle(heights)` returns the maximum area of an axis-aligned rectangle that fits under
  the given histogram, given an array of `heights` where each bar has width 1.

Time Complexity:
- O(n) per call to all functions, where $n$ is the size of the input.

Space Complexity:
- O(n) auxiliary heap space for the stack and result.

*/

#include <stack>
#include <vector>

template<class T>
std::vector<int> previous_less(const std::vector<T> &a) {
  int n = static_cast<int>(a.size());
  std::vector<int> res(n);
  std::stack<int> s;
  for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] >= a[i]) {
      s.pop();
    }
    res[i] = s.empty() ? -1 : s.top();
    s.push(i);
  }
  return res;
}

template<class T>
std::vector<int> next_less(const std::vector<T> &a) {
  int n = static_cast<int>(a.size());
  std::vector<int> res(n);
  std::stack<int> s;
  for (int i = n - 1; i >= 0; i--) {
    while (!s.empty() && a[s.top()] >= a[i]) {
      s.pop();
    }
    res[i] = s.empty() ? n : s.top();
    s.push(i);
  }
  return res;
}

template<class T>
std::vector<int> previous_greater(const std::vector<T> &a) {
  int n = static_cast<int>(a.size());
  std::vector<int> res(n);
  std::stack<int> s;
  for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] <= a[i]) {
      s.pop();
    }
    res[i] = s.empty() ? -1 : s.top();
    s.push(i);
  }
  return res;
}

template<class T>
std::vector<int> next_greater(const std::vector<T> &a) {
  int n = static_cast<int>(a.size());
  std::vector<int> res(n);
  std::stack<int> s;
  for (int i = n - 1; i >= 0; i--) {
    while (!s.empty() && a[s.top()] <= a[i]) {
      s.pop();
    }
    res[i] = s.empty() ? n : s.top();
    s.push(i);
  }
  return res;
}

template<class T>
T largest_rectangle(const std::vector<T> &heights) {
  int n = static_cast<int>(heights.size());
  std::vector<int> left = previous_less(heights), right = next_less(heights);
  T best = 0;
  for (int i = 0; i < n; i++) {
    T area = heights[i] * (right[i] - left[i] - 1);
    if (area > best) {
      best = area;
    }
  }
  return best;
}

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  vector<int> a{2, 1, 4, 3};
  assert((previous_less(a) == vector<int>{-1, -1, 1, 1}));
  assert((next_less(a) == vector<int>{1, 4, 3, 4}));
  assert((previous_greater(a) == vector<int>{-1, 0, -1, 2}));
  assert((next_greater(a) == vector<int>{2, 2, 4, 4}));

  vector<int> hist{2, 1, 5, 6, 2, 3};
  assert(largest_rectangle(hist) == 10);
  return 0;
}