Contribution / boundaries (Monotonic Stack Sub-pattern)
For each element, find how far it stretches left and right while staying the minimum (or maximum): its previous smaller and next smaller. Then each element's contribution can be counted directly instead of looking at every subarray.
- ›
"largest rectangle in a histogram" / "largest rectangle of 1s"
- ›
"sum of the minimum of every subarray"
- ›
"sum of (max − min) over all subarrays"
- ›
the brute force loops over all O(N²) subarrays
Largest Rectangle wants a max: area = h × (right − left − 1); ties don't matter. Sum of Subarray Minimums wants a sum: a[i] × (i − left) × (right − i), and the tie rule (strict on one side only) matters. Sum of Subarray Ranges is that twice: Σ max − Σ min. Maximal Rectangle builds a histogram row by row and reuses Largest Rectangle. Trapping Rain Water (linked; taught with two pointers) also has a stack solution: when a taller bar arrives, pop the bottom and fill water above it up to the lower of its two walls.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Largest Rectangle in HistogramWalkthroughHardBasic Anchor·LeetCode #84
- 2Sum of Subarray MinimumsWalkthroughMediumBasic Reinforcement·LeetCode #907
- 3Sum of Subarray RangesWalkthroughMediumSlight Variation·LeetCode #2104
- 4Maximal RectangleWalkthroughHardPattern Transfer·LeetCode #85
- 5Trapping Rain Water (stack approach)WalkthroughHardTricky / Edge Case·LeetCode #42
Template
// Sum of min(subarray) over all subarrays: each a[i] counts as the minimum
// of (i - left[i]) * (right[i] - i) subarrays.
long long sumOfSubarrayMins(vector<int>& a) {
int n = a.size();
vector<int> left(n), right(n);
stack<int> st;
for (int i = 0; i < n; i++) { // previous STRICTLY smaller
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
st = stack<int>();
for (int i = n - 1; i >= 0; i--) { // next smaller OR EQUAL
while (!st.empty() && a[st.top()] > a[i]) st.pop();
right[i] = st.empty() ? n : st.top();
st.push(i);
}
long long total = 0;
for (int i = 0; i < n; i++)
total += (long long)a[i] * (i - left[i]) * (right[i] - i);
return total; // (LC 907 also wants % 1e9+7)
}