Monotonic Stack

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute Next Greater Element for each index. If none exists, answer is -1.
5
// Time: O(n), Space: O(n)
6
vector<int> nextGreaterElement(const vector<int>& a) {
7
    int n = (int)a.size();
8
    vector<int> ans(n, -1);
9
    stack<int> st; // stack of indices, values strictly decreasing on stack
10
    for (int i = 0; i < n; ++i) {
11
        // Resolve all indices whose next greater is a[i]
12
        while (!st.empty() && a[i] > a[st.top()]) {
13
            ans[st.top()] = a[i];
14
            st.pop();
15
        }
16
        st.push(i);
17
    }
18
    // Remaining indices have no next greater; already -1
19
    return ans;
20
}
21
22
int main() {
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
26
    vector<int> a = {2, 1, 2, 4, 3};
27
    vector<int> nge = nextGreaterElement(a);
28
29
    cout << "Array: ";
30
    for (int x : a) cout << x << ' ';
31
    cout << "\nNext Greater: ";
32
    for (int x : nge) cout << x << ' ';
33
    cout << "\n";
34
    return 0;
35
}
36

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute the largest rectangle in a histogram using a monotonic increasing stack.
5
// Time: O(n), Space: O(n)
6
long long largestRectangleArea(vector<int> h) {
7
    // Append a sentinel 0 height to flush the stack at the end
8
    h.push_back(0);
9
    int n = (int)h.size();
10
    stack<int> st; // indices with increasing heights
11
    long long best = 0;
12
    for (int i = 0; i < n; ++i) {
13
        // Maintain increasing stack; when current is lower, resolve areas
14
        while (!st.empty() && h[i] < h[st.top()]) {
15
            int mid = st.top(); st.pop();
16
            long long height = h[mid];
17
            // After popping mid, the new top is the previous smaller to the left
18
            int leftBoundary = st.empty() ? 0 : st.top() + 1; // first index where height >= current height becomes left boundary + 1
19
            int rightBoundaryExclusive = i; // current i is the first smaller to the right
20
            long long width = rightBoundaryExclusive - leftBoundary;
21
            best = max(best, height * width);
22
        }
23
        st.push(i);
24
    }
25
    return best;
26
}
27
28
int main() {
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    vector<int> h = {2, 1, 5, 6, 2, 3};
33
    cout << largestRectangleArea(h) << "\n"; // Expected: 10 (bars 5 and 6)
34
    return 0;
35
}
36

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute total trapped water using a monotonic decreasing stack of indices.
5
// Time: O(n), Space: O(n)
6
long long trap(const vector<int>& h) {
7
    int n = (int)h.size();
8
    stack<int> st; // decreasing heights: h[st[0]] >= h[st[1]] >= ...
9
    long long water = 0;
10
    for (int i = 0; i < n; ++i) {
11
        // When we find a right wall higher than the basin bottom, close basins
12
        while (!st.empty() && h[i] > h[st.top()]) {
13
            int bottom = st.top(); st.pop();
14
            // If no left wall, cannot trap water yet
15
            if (st.empty()) break;
16
            int left = st.top();
17
            int width = i - left - 1; // distance between walls excluding them
18
            int boundedHeight = min(h[left], h[i]) - h[bottom];
19
            if (boundedHeight > 0) water += 1LL * width * boundedHeight;
20
        }
21
        st.push(i);
22
    }
23
    return water;
24
}
25
26
int main() {
27
    ios::sync_with_stdio(false);
28
    cin.tie(nullptr);
29
30
    vector<int> h = {0,1,0,2,1,0,1,3,2,1,2,1};
31
    cout << trap(h) << "\n"; // Expected: 6
32
    return 0;
33
}
34

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Largest rectangle in histogram helper (same as previous example, slightly refactored)
5
long long largestRectangleArea(const vector<int>& h) {
6
    vector<int> a = h;
7
    a.push_back(0);
8
    stack<int> st;
9
    long long best = 0;
10
    for (int i = 0; i < (int)a.size(); ++i) {
11
        while (!st.empty() && a[i] < a[st.top()]) {
12
            int mid = st.top(); st.pop();
13
            long long height = a[mid];
14
            int left = st.empty() ? 0 : st.top() + 1;
15
            int width = i - left;
16
            best = max(best, height * 1LL * width);
17
        }
18
        st.push(i);
19
    }
20
    return best;
21
}
22
23
// Maximal rectangle of 1s in a binary matrix using histogram heights per row.
24
// Time: O(R*C), Space: O(C)
25
long long maximalRectangle(const vector<string>& grid) {
26
    if (grid.empty()) return 0;
27
    int R = (int)grid.size();
28
    int C = (int)grid[0].size();
29
    vector<int> height(C, 0);
30
    long long ans = 0;
31
    for (int r = 0; r < R; ++r) {
32
        for (int c = 0; c < C; ++c) {
33
            if (grid[r][c] == '1') height[c] += 1; else height[c] = 0;
34
        }
35
        ans = max(ans, largestRectangleArea(height));
36
    }
37
    return ans;
38
}
39
40
int main() {
41
    ios::sync_with_stdio(false);
42
    cin.tie(nullptr);
43
44
    vector<string> grid = {
45
        "10100",
46
        "10111",
47
        "11111",
48
        "10010"
49
    };
50
    cout << maximalRectangle(grid) << "\n"; // Expected: 6
51
    return 0;
52
}
53