A value that a bigger one has passed can never be an answer again, so throw it away. What is left on the stack is sorted, without ever sorting. Each value is pushed once and popped once, and an O(n²) scan becomes O(n). Nine moves, fifteen problems.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.
A day waits on the stack until a warmer day arrives. The warmer day pops it, and the gap i − j is its answer.
nums2 = [2, 7, 3, 5, 4, 6, 8]. What is the next greater element of 3?
5 is the first value after 3 that is bigger. 3 waits on the stack until 5 pops it.
When the scan ends, which values are still on the stack?
Nothing bigger came after them, so nothing popped them. Their answer is −1, or 0 days.
For each value, the first greater value to its right. The queries come from a second array, so answer every value once and look the queries up.
Read nums2 once. A value waits on the stack until a bigger one arrives, and that arrival is its answer. Store the answers in a map.
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> nxt; // value → its next greater vector<int> st; // values still waiting for (int x : nums2) { while (!st.empty() && st.back() < x) { nxt[st.back()] = x; // x is the first bigger one st.pop_back(); } st.push_back(x); } vector<int> ans; for (int x : nums1) ans.push_back(nxt.count(x) ? nxt[x] : -1); return ans; }
public int[] nextGreaterElement(int[] nums1, int[] nums2) { Map<Integer, Integer> nxt = new HashMap<>(); // value → its next greater Deque<Integer> st = new ArrayDeque<>(); // values still waiting for (int x : nums2) { while (!st.isEmpty() && st.peek() < x) nxt.put(st.pop(), x); st.push(x); } int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) ans[i] = nxt.getOrDefault(nums1[i], -1); return ans; }
def nextGreaterElement(nums1, nums2): nxt, st = {}, [] # value → next greater; values waiting for x in nums2: while st and st[-1] < x: nxt[st.pop()] = x # x is the first bigger one st.append(x) return [nxt.get(x, -1) for x in nums1]
Searching nums2 once per query. Finding x and scanning right from it is O(n · m). One pass over nums2 answers every value at once.
“How many days until a warmer one?” A distance to the next greater value, so the stack must hold indices, not temperatures.
A day waits on the stack until a warmer day pops it. The gap between the two indices is the answer. Days still waiting at the end keep 0.
vector<int> dailyTemperatures(vector<int>& temperatures) { vector<int>& t = temperatures; int n = t.size(); vector<int> ans(n, 0), st; // st: days still waiting for (int i = 0; i < n; i++) { while (!st.empty() && t[st.back()] < t[i]) { ans[st.back()] = i - st.back(); // day i is the warmer one st.pop_back(); } st.push_back(i); } return ans; // days left waiting keep 0 }
public int[] dailyTemperatures(int[] temperatures) { int[] t = temperatures; int n = t.length, top = 0; int[] ans = new int[n], st = new int[n]; // st: days still waiting for (int i = 0; i < n; i++) { while (top > 0 && t[st[top - 1]] < t[i]) { int j = st[--top]; ans[j] = i - j; // day i is the warmer one } st[top++] = i; } return ans; // days left waiting keep 0 }
def dailyTemperatures(temperatures): t = temperatures ans, st = [0] * len(t), [] # st: days still waiting for i, x in enumerate(t): while st and t[st[-1]] < x: j = st.pop() ans[j] = i - j # day i is the warmer one st.append(i) return ans # days left waiting keep 0
Pushing the temperature. The answer is a distance, so the stack needs the day. With indices on the stack, t[st.back()] still gives the temperature.
dailyTemperatures([30, 40, 50, 60])?
Each day is popped by the very next one. The last day is never popped, so it keeps 0.
Person i sees person j when everyone between them is shorter than both. Count, for each person, how many they see to the right.
Walk from the right. The people i could see are on a stack, taller toward the bottom. Each shorter one on top is seen by i and then hidden behind i, so pop it. The first taller one is seen too, and blocks the rest.
vector<int> canSeePersonsCount(vector<int>& heights) { int n = heights.size(); vector<int> ans(n), st; // heights to the right, taller below for (int i = n - 1; i >= 0; i--) { int seen = 0; while (!st.empty() && st.back() < heights[i]) { st.pop_back(); // seen by i, then hidden by i seen++; } if (!st.empty()) seen++; // the first person taller than i ans[i] = seen; st.push_back(heights[i]); } return ans; }
public int[] canSeePersonsCount(int[] heights) { int n = heights.length, top = 0; int[] ans = new int[n], st = new int[n]; // heights to the right, taller below for (int i = n - 1; i >= 0; i--) { int seen = 0; while (top > 0 && st[top - 1] < heights[i]) { top--; seen++; } if (top > 0) seen++; // the first person taller than i ans[i] = seen; st[top++] = heights[i]; } return ans; }
def canSeePersonsCount(heights): ans, st = [0] * len(heights), [] # heights to the right, taller below for i in range(len(heights) - 1, -1, -1): seen = 0 while st and st[-1] < heights[i]: st.pop() # seen by i, then hidden by i seen += 1 if st: seen += 1 # the first person taller than i ans[i] = seen st.append(heights[i]) return ans
Forgetting the one who blocks. The pops count the shorter people, and the first taller person is seen as well. Without the +1, every answer is one short except where nobody taller is left.
heights = [5, 1, 2, 3, 10]. How many people does the first one, of height 5, see?
Everyone between 5 and each of 1, 2, 3 and 10 is shorter than both. Nobody stands after 10.
Read nums[i % n] for i up to 2n − 1. The first lap pushes and answers; the second lap only answers.
nextGreaterElements([5, 4, 3, 2, 1])?
Going round, every value meets the 5 at the start. Nothing is bigger than 5 itself.
Why does the second lap not push?
Every index was pushed on the first lap. The second lap only lets the ones still waiting see the values before them.
The array is circular: after the last value, the search for a greater one goes on from the start.
Read the array twice, index i % n. The first lap pushes and answers; the second lap only answers, so no index waits twice.
vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> ans(n, -1), st; // st: indices still waiting for (int i = 0; i < 2 * n; i++) { // read the array twice int x = nums[i % n]; while (!st.empty() && nums[st.back()] < x) { ans[st.back()] = x; st.pop_back(); } if (i < n) st.push_back(i); // only the first lap pushes } return ans; // never answered: still −1 }
public int[] nextGreaterElements(int[] nums) { int n = nums.length, top = 0; int[] ans = new int[n], st = new int[n]; // st: indices still waiting Arrays.fill(ans, -1); for (int i = 0; i < 2 * n; i++) { // read the array twice int x = nums[i % n]; while (top > 0 && nums[st[top - 1]] < x) ans[st[--top]] = x; if (i < n) st[top++] = i; // only the first lap pushes } return ans; }
def nextGreaterElements(nums): n = len(nums) ans, st = [-1] * n, [] # st: indices still waiting for i in range(2 * n): # read the array twice x = nums[i % n] while st and nums[st[-1]] < x: ans[st.pop()] = x if i < n: st.append(i) # only the first lap pushes return ans
One lap. A value near the end whose next greater is back at the start is never answered: [1, 2, 1] gives [2, −1, −1] instead of [2, −1, 2].
Each entry is (price, span). Today absorbs every price on top that is at most its own, and their spans add up.
A StockSpanner gets 31, 41, 48, 59 and 79, in that order. What does the last call return?
Every price so far is at most 79. It absorbs (59, 4), so its span is 1 + 4.
Each call adds today's price and asks how many days in a row, ending today, the price was at most today's.
Keep (price, span) pairs, prices falling toward the top. Today absorbs every pair on top with a price at most its own, and adds up their spans.
class StockSpanner { vector<pair<int, int>> st; // (price, span), prices fall upward public: StockSpanner() {} int next(int price) { int span = 1; // today while (!st.empty() && st.back().first <= price) { span += st.back().second; // absorb its days st.pop_back(); } st.push_back({price, span}); return span; } };
class StockSpanner { private final Deque<int[]> st = new ArrayDeque<>(); // {price, span} public StockSpanner() {} public int next(int price) { int span = 1; // today while (!st.isEmpty() && st.peek()[0] <= price) span += st.pop()[1]; st.push(new int[]{price, span}); return span; } }
class StockSpanner: def __init__(self): self.st = [] # (price, span), prices fall upward def next(self, price): span = 1 # today while self.st and self.st[-1][0] <= price: span += self.st.pop()[1] # absorb its days self.st.append((price, span)) return span
Popping without keeping the span. A popped pair stands for every day it absorbed. Adding 1 per pop instead of its span undercounts as soon as two absorbs chain.
For every position, the nearest position to its left with a smaller value, or 0. Positions count from 1.
Scan left to right with a stack of positions whose values rise toward the top. Pop every value at least x[i]: it can never be the answer for i or anything after i. The top is then i's answer.
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> x(n), st; // st: positions, values rising upward for (int& v : x) cin >> v; string out; for (int i = 0; i < n; i++) { while (!st.empty() && x[st.back()] >= x[i]) st.pop_back(); // never again out += to_string(st.empty() ? 0 : st.back() + 1); // 1-based, or 0 out += i + 1 < n ? ' ' : '\n'; st.push_back(i); } cout << out; }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval, top = 0; int[] x = new int[n], st = new int[n]; // st: positions, values rising upward for (int i = 0; i < n; i++) { in.nextToken(); x[i] = (int) in.nval; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { while (top > 0 && x[st[top - 1]] >= x[i]) top--; // never again sb.append(top == 0 ? 0 : st[top - 1] + 1).append(i + 1 < n ? ' ' : '\n'); st[top++] = i; } System.out.print(sb); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) x = list(map(int, data[1:1 + n])) st, out = [], [] # st: positions, values rising upward for i in range(n): while st and x[st[-1]] >= x[i]: st.pop() # not smaller: never an answer again out.append(st[-1] + 1 if st else 0) # 1-based, or 0 st.append(i) print(" ".join(map(str, out))) main()
Popping only the larger values. An equal value is not smaller, so it is never an answer. Testing > instead of >= prints its position.
Nearest Smaller Values on 3 1 4 1 5, with positions from 1?
The second 1 is not smaller than the first, so it gets 0. The 5 sees the 1 beside it.
A solution pops while x[top] > x[i]. What does it print on 2 2?
The first 2 stays on the stack, so the second prints position 1. But 2 is not smaller than 2; the answer is 0 0.
A left-mover meets the newest right-mover first. It breaks smaller ones until it breaks, ties, or nothing is left to hit.
Sort closest first and work out when each car would arrive alone. No later than the fleet ahead: it joins. Later: a new fleet.
asteroidCollision([5, 10, −5])?
−5 meets 10 first, and 10 is bigger, so −5 breaks. It never reaches the 5.
asteroidCollision([−2, −1, 1, 2])?
The left-movers are already on the left and the right-movers on the right. Nothing meets.
Asteroids move at one speed; a sign gives the direction. A collision needs a right-mover on the left meeting a left-mover on the right.
The survivors so far are a stack. Only a left-mover can collide, and it meets the top survivor first. It keeps breaking smaller right-movers until it breaks, ties, or reaches a left-mover or nothing.
vector<int> asteroidCollision(vector<int>& asteroids) { vector<int> st; // the survivors so far for (int x : asteroids) { bool alive = true; while (alive && x < 0 && !st.empty() && st.back() > 0) { if (st.back() < -x) { st.pop_back(); continue; } // the → breaks if (st.back() == -x) st.pop_back(); // both break alive = false; // x breaks } if (alive) st.push_back(x); } return st; }
public int[] asteroidCollision(int[] asteroids) { int[] st = new int[asteroids.length]; // the survivors so far int top = 0; for (int x : asteroids) { boolean alive = true; while (alive && x < 0 && top > 0 && st[top - 1] > 0) { if (st[top - 1] < -x) { top--; continue; } // the → breaks if (st[top - 1] == -x) top--; // both break alive = false; // x breaks } if (alive) st[top++] = x; } return Arrays.copyOf(st, top); }
def asteroidCollision(asteroids): st = [] # the survivors so far for x in asteroids: alive = True while alive and x < 0 and st and st[-1] > 0: if st[-1] < -x: st.pop() # the → breaks; x flies on continue if st[-1] == -x: st.pop() # both break alive = False # x breaks if alive: st.append(x) return st
Letting a left-mover hit another left-mover. [−2, −1] never collides: they move the same way. The loop must also check that the top moves right.
Cars on one road, no overtaking. A car that catches a slower car ahead joins it and drives at its speed. Count the groups that arrive.
Sort by position, closest to the target first, and work out when each car would arrive alone. A car that would arrive no later than the fleet ahead catches it. A later one starts a new fleet.
int carFleet(int target, vector<int>& position, vector<int>& speed) { vector<pair<int, int>> car; for (int i = 0; i < position.size(); i++) car.push_back({position[i], speed[i]}); sort(car.rbegin(), car.rend()); // closest to the target first long long d = 0, s = 1; // the fleet ahead arrives at d / s int fleets = 0; for (auto& c : car) { long long dc = target - c.first; // this car would arrive at dc / c.second if (fleets == 0 || dc * s > d * c.second) { // later, exactly: a new fleet fleets++; d = dc; s = c.second; } } return fleets; }
public int carFleet(int target, int[] position, int[] speed) { int n = position.length, fleets = 0; Integer[] order = new Integer[n]; for (int i = 0; i < n; i++) order[i] = i; Arrays.sort(order, (a, b) -> position[b] - position[a]); // closest first double ahead = -1; // the arrival time of the fleet ahead for (int i : order) { double t = (double) (target - position[i]) / speed[i]; if (t > ahead) { fleets++; ahead = t; } // too slow to catch it: a new fleet } return fleets; }
def carFleet(target, position, speed): st = [] # each fleet's arrival time for p, s in sorted(zip(position, speed), reverse=True): # closest first t = (target - p) / s if not st or t > st[-1]: # too slow to catch the fleet ahead st.append(t) # so it leads a new one return len(st)
Sorting by speed, or not sorting. Whether a car catches another depends on who is ahead, so the order must be by position. In input order, a car can be compared with one behind it.
target = 10, position = [6, 8], speed = [3, 2]. How many fleets?
The car at 8 arrives at t = 1. The car at 6 needs 4 / 3, so it never catches up.
target = 10, position = [0, 4, 2], speed = [2, 1, 3]. How many fleets?
The car at 4 needs t = 6. The others would arrive at 8 / 3 and 5, both sooner, so both catch it.
While k lasts, a digit bigger than the next is popped. The stack never falls, and any removals left over come off the end.
removeKdigits("10200", 1)?
1 is bigger than the 0 after it, so it goes. The leading 0 of 0200 is then stripped.
removeKdigits("12345", 2)?
The digits rise, so nothing is popped. Both removals come off the end.
Remove k digits to leave the smallest number. The leftmost digits weigh the most.
A digit bigger than the one after it should go, while removals are left. Keep the answer on a stack that never falls. Leftover removals come off the end, and leading zeros are stripped.
string removeKdigits(string num, int k) { string st; // the answer so far, never falling for (char c : num) { while (k > 0 && !st.empty() && st.back() > c) { st.pop_back(); // a bigger digit before a smaller one k--; } st.push_back(c); } while (k > 0) { st.pop_back(); k--; } // still owed: cut from the end int i = 0; while (i < st.size() && st[i] == '0') i++; string r = st.substr(i); return r.empty() ? "0" : r; }
public String removeKdigits(String num, int k) { StringBuilder st = new StringBuilder(); // the answer so far, never falling for (char c : num.toCharArray()) { while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > c) { st.deleteCharAt(st.length() - 1); // a bigger digit before a smaller one k--; } st.append(c); } st.setLength(st.length() - k); // still owed: cut from the end int i = 0; while (i < st.length() && st.charAt(i) == '0') i++; String r = st.substring(i); return r.isEmpty() ? "0" : r; }
def removeKdigits(num, k): st = [] # the answer so far, never falling for c in num: while k and st and st[-1] > c: st.pop() # a bigger digit before a smaller one k -= 1 st.append(c) if k: del st[-k:] # still owed: cut from the end return "".join(st).lstrip("0") or "0" # strip the leading zeros
Forgetting the leftover k. On a rising number such as 12345 nothing is ever popped. The k removals are still owed and come off the end.
When i pops j, the new top is j's left edge and i its right. arr[j] is the minimum of (j − left) · (i − j) subarrays.
arr = [2, 2]. Counted at the pop, how many subarrays does each 2 get?
The first gets [2]. The second gets its own [2] and [2, 2], because its left edge is −1. Three subarrays, each counted once.
sumSubarrayMins([1, 2, 3])?
The minima are 1, 2, 3, 1, 2 and 1. The 1 is the minimum of three subarrays, the 2 of two.
The sum of the minimum of every subarray. There are n² / 2 subarrays, so count, for each element, how many of them it is the minimum of.
arr[j] is the minimum of every subarray that starts after the previous smaller value and ends before the next smaller-or-equal one. A stack of rising values finds both edges the moment j is popped.
int sumSubarrayMins(vector<int>& arr) { const long long MOD = 1000000007; int n = arr.size(); long long sum = 0; vector<int> st; // indices, values rise toward the top for (int i = 0; i <= n; i++) { // i == n: a 0 that pops everything int x = i < n ? arr[i] : 0; while (!st.empty() && arr[st.back()] >= x) { int j = st.back(); st.pop_back(); int left = st.empty() ? -1 : st.back(); sum = (sum + (long long)arr[j] * (j - left) * (i - j)) % MOD; } st.push_back(i); } return sum; }
public int sumSubarrayMins(int[] arr) { final long MOD = 1_000_000_007L; int n = arr.length, top = 0; int[] st = new int[n + 1]; // indices, values rise toward the top long sum = 0; for (int i = 0; i <= n; i++) { // i == n: a 0 that pops everything int x = i < n ? arr[i] : 0; while (top > 0 && arr[st[top - 1]] >= x) { int j = st[--top]; int left = top > 0 ? st[top - 1] : -1; sum = (sum + (long) arr[j] * (j - left) * (i - j)) % MOD; } st[top++] = i; } return (int) sum; }
def sumSubarrayMins(arr): n, total, st = len(arr), 0, [] # st: indices, values rise upward for i in range(n + 1): x = arr[i] if i < n else 0 # i == n: a 0 that pops everything while st and arr[st[-1]] >= x: j = st.pop() left = st[-1] if st else -1 total += arr[j] * (j - left) * (i - j) # starts × ends st.append(i) return total % (10**9 + 7)
Counting a tie twice. With equal values, one side must stop at “smaller” and the other at “smaller or equal”. The single stack does this already: left is strictly smaller, because an equal value was popped.
The sum of max − min over every subarray. Split it: the sum of the maxima minus the sum of the minima.
Each sum is unit 6 again. Run the contribution stack twice: once with values falling toward the top, adding each maximum's share, and once rising, taking off each minimum's.
long long subArrayRanges(vector<int>& nums) { int n = nums.size(); long long total = 0; for (int sign : {1, -1}) { // +1 adds the maxima, −1 takes the minima vector<int> st; for (int i = 0; i <= n; i++) { while (!st.empty() && (i == n || sign * nums[st.back()] <= sign * nums[i])) { int j = st.back(); st.pop_back(); int left = st.empty() ? -1 : st.back(); total += (long long)sign * nums[j] * (j - left) * (i - j); } st.push_back(i); } } return total; }
public long subArrayRanges(int[] nums) { int n = nums.length; long total = 0; for (int sign : new int[]{1, -1}) { // +1 adds the maxima, −1 takes the minima int[] st = new int[n + 1]; int top = 0; for (int i = 0; i <= n; i++) { while (top > 0 && (i == n || sign * nums[st[top - 1]] <= sign * nums[i])) { int j = st[--top]; int left = top > 0 ? st[top - 1] : -1; total += (long) sign * nums[j] * (j - left) * (i - j); } st[top++] = i; } } return total; }
def subArrayRanges(nums): n, total = len(nums), 0 for sign in (1, -1): # +1 adds the maxima, −1 takes the minima st = [] for i in range(n + 1): while st and (i == n or sign * nums[st[-1]] <= sign * nums[i]): j = st.pop() left = st[-1] if st else -1 total += sign * nums[j] * (j - left) * (i - j) st.append(i) return total
A 32-bit total. One share can be 10⁹ · 500 · 500. The sum, and the product that makes each share, need long long before the multiply.
subArrayRanges([1, 3, 2])?
The single values give 0. Then [1, 3] gives 2, [3, 2] gives 1 and [1, 3, 2] gives 2.
A lower bar pops each taller one. The popped bar's rectangle runs from just after the bar below it to just before the popper.
largestRectangleArea([2, 4])?
Height 2 across both bars is 4, and height 4 on its own is also 4.
heights = [6, 2, 5, 4, 5, 1, 6]. The 1 at index 5 pops the bar of 4 at index 3. How wide is that bar's rectangle?
The bar below it on the stack is the 2 at index 1. So it spans indices 2 to 4, and its area is 12.
The largest rectangle under a histogram. Every rectangle is as tall as its lowest bar, so try each bar as that lowest one.
A bar's rectangle spreads left and right until a lower bar. Keep bars on a stack, rising toward the top. A lower bar pops each taller one, and the bar below it on the stack is its left edge.
int largestRectangleArea(vector<int>& heights) { vector<int>& h = heights; int n = h.size(), best = 0; vector<int> st; // bars still growing, rising upward for (int i = 0; i <= n; i++) { // i == n: a bar of 0 ends them all int x = i < n ? h[i] : 0; while (!st.empty() && h[st.back()] >= x) { int j = st.back(); st.pop_back(); int left = st.empty() ? -1 : st.back(); best = max(best, h[j] * (i - left - 1)); } st.push_back(i); } return best; }
public int largestRectangleArea(int[] heights) { int n = heights.length, best = 0, top = 0; int[] st = new int[n + 1]; // bars still growing, rising upward for (int i = 0; i <= n; i++) { // i == n: a bar of 0 ends them all int x = i < n ? heights[i] : 0; while (top > 0 && heights[st[top - 1]] >= x) { int j = st[--top]; int left = top > 0 ? st[top - 1] : -1; best = Math.max(best, heights[j] * (i - left - 1)); } st[top++] = i; } return best; }
def largestRectangleArea(heights): h = heights + [0] # a bar of 0 ends them all best, st = 0, [] # bars still growing, rising upward for i, x in enumerate(h): while st and h[st[-1]] >= x: j = st.pop() left = st[-1] if st else -1 best = max(best, h[j] * (i - left - 1)) st.append(i) return best
Width i − j. That measures only from j rightwards. Bars to the left of j that are taller were popped earlier and still belong to its rectangle. The left edge is the bar below j on the stack.
For every group size x from 1 to n, find the largest possible minimum of a group of x neighbouring bears.
Turn it round. a[j] is the minimum of a run of exactly w bears, the run unit 7 measures. So best[w] ≥ a[j]. A size that fits in a run also fits in any longer one, so a sweep from the largest size down finishes it.
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n + 1, 0), best(n + 2, 0), st; // a[n] = 0 ends every run for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i <= n; i++) { while (!st.empty() && a[st.back()] >= a[i]) { int j = st.back(); st.pop_back(); int left = st.empty() ? -1 : st.back(); int w = i - left - 1; // a[j] is the minimum of a run this wide best[w] = max(best[w], a[j]); } st.push_back(i); } for (int x = n - 1; x >= 1; x--) best[x] = max(best[x], best[x + 1]); for (int x = 1; x <= n; x++) cout << best[x] << (x < n ? ' ' : '\n'); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval, top = 0; int[] a = new int[n + 1], best = new int[n + 2], st = new int[n + 1]; // a[n] = 0 for (int i = 0; i < n; i++) { in.nextToken(); a[i] = (int) in.nval; } for (int i = 0; i <= n; i++) { while (top > 0 && a[st[top - 1]] >= a[i]) { int j = st[--top]; int left = top > 0 ? st[top - 1] : -1; int w = i - left - 1; // a[j] is the minimum of a run this wide best[w] = Math.max(best[w], a[j]); } st[top++] = i; } for (int x = n - 1; x >= 1; x--) best[x] = Math.max(best[x], best[x + 1]); StringBuilder sb = new StringBuilder(); for (int x = 1; x <= n; x++) sb.append(best[x]).append(x < n ? ' ' : '\n'); System.out.print(sb); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) a = list(map(int, data[1:1 + n])) + [0] # a[n] = 0 ends every run best, st = [0] * (n + 2), [] for i in range(n + 1): while st and a[st[-1]] >= a[i]: j = st.pop() left = st[-1] if st else -1 w = i - left - 1 # a[j] is the minimum of a run this wide if a[j] > best[w]: best[w] = a[j] st.append(i) for x in range(n - 1, 0, -1): best[x] = max(best[x], best[x + 1]) # a shorter group fits inside print(" ".join(map(str, best[1:n + 1]))) main()
Skipping the sweep. Some sizes are never a run's exact width, and their best stays 0. The answer for x is at least the answer for x + 1, so carry it down.
Mike and Feet with n = 3 and heights 3 1 2. What is printed?
For size 1 the best is the 3 alone. Every group of 2 or 3 contains the 1.
A solution leaves out the backward sweep. What does it print on 2 1 2?
No run is exactly 2 wide, so best[2] stays 0. The sweep would carry best[3] = 1 down to it.
Values fall from front to back. A bigger arrival removes the smaller ones behind it, and the front leaves when the window passes it.
maxSlidingWindow([9, 8, 7, 6], 2)?
Each window's maximum is its first value. Nothing is popped from the back; the front leaves as the window passes it.
How many indices can the deque hold at once?
Every index in it is inside the window, and the window holds k.
nums = [4, 2, 3], k = 3. Which values are in the deque, front to back, after i = 2?
3 removes the 2 behind it, which can never be a maximum again. 4 is bigger, so it stays in front.
The maximum of every window of size k. A max-heap would cost log k per step; the window only ever loses its oldest value.
Keep indices in a deque with values falling from front to back. A value with a bigger one after it can never be a maximum again, so it leaves from the back. The front leaves once it is out of the window, and the front is always the maximum.
vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; // indices; values fall front to back vector<int> out; for (int i = 0; i < nums.size(); i++) { if (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // out of the window while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); // smaller and older: never a maximum dq.push_back(i); if (i >= k - 1) out.push_back(nums[dq.front()]); } return out; }
public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length, head = 0, tail = 0; int[] dq = new int[n], out = new int[n - k + 1]; // dq[head..tail): indices for (int i = 0; i < n; i++) { if (head < tail && dq[head] <= i - k) head++; // out of the window while (head < tail && nums[dq[tail - 1]] <= nums[i]) tail--; // smaller and older: never a maximum dq[tail++] = i; if (i >= k - 1) out[i - k + 1] = nums[dq[head]]; } return out; }
from collections import deque def maxSlidingWindow(nums, k): dq, out = deque(), [] # indices; values fall front to back for i, x in enumerate(nums): if dq and dq[0] <= i - k: dq.popleft() # out of the window while dq and nums[dq[-1]] <= x: dq.pop() # smaller and older: never a maximum dq.append(i) if i >= k - 1: out.append(nums[dq[0]]) return out
Storing values in the deque. Then nothing says when the front has left the window, and a repeated value makes it worse. Store indices and read the values through them.
P rises along the deque. A front start that already reaches k is recorded and dropped; a back start with P ≥ P[j] can never win.
Why can a sliding window not solve this problem?
Shrinking a window can raise its sum, and growing it can lower it. A window only works when growing never lowers the sum.
nums = [2, −1, 2], k = 3. What is P, and the answer?
Only the whole array reaches 3: P[3] − P[0] = 3. P starts with the empty prefix, 0.
Start s leaves the back of the deque when P[s] ≥ P[j]. Why can s never be the best start?
For any later end, j gives a sum at least as large from a shorter subarray.
The shortest subarray with sum ≥ k, and the values can be negative. A sliding window fails: growing a window can lower its sum.
A sum is P[j] − P[s] over prefix sums. Keep start candidates in a deque with P rising. From the front, take every start that already reaches k, since no later end can beat it. From the back, drop a start whose P is at least P[j]: j starts later with a smaller prefix.
int shortestSubarray(vector<int>& nums, int k) { int n = nums.size(); vector<long long> P(n + 1, 0); for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i]; deque<int> dq; // starts; P rises front to back int best = INT_MAX; for (int j = 0; j <= n; j++) { while (!dq.empty() && P[j] - P[dq.front()] >= k) { best = min(best, j - dq.front()); // the shortest from this start dq.pop_front(); } while (!dq.empty() && P[dq.back()] >= P[j]) dq.pop_back(); // later and smaller: always better dq.push_back(j); } return best == INT_MAX ? -1 : best; }
public int shortestSubarray(int[] nums, int k) { int n = nums.length, head = 0, tail = 0, best = n + 1; long[] P = new long[n + 1]; for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i]; int[] dq = new int[n + 1]; // starts; P rises front to back for (int j = 0; j <= n; j++) { while (head < tail && P[j] - P[dq[head]] >= k) best = Math.min(best, j - dq[head++]); // the shortest from this start while (head < tail && P[dq[tail - 1]] >= P[j]) tail--; // later and smaller: always better dq[tail++] = j; } return best <= n ? best : -1; }
from collections import deque def shortestSubarray(nums, k): P = [0] for x in nums: P.append(P[-1] + x) dq, best = deque(), len(nums) + 1 # starts; P rises front to back for j in range(len(P)): while dq and P[j] - P[dq[0]] >= k: best = min(best, j - dq.popleft()) # the shortest from this start while dq and P[dq[-1]] >= P[j]: dq.pop() # later and smaller: always better dq.append(j) return best if best <= len(nums) else -1
A sliding window. With negatives, shrinking from the left can raise the sum and growing can lower it, so a window misses answers. On [84, −37, 32, 40, 95] with k = 167 the answer is the last three values; a window returns 5.
Nine moves, and each has a phrase in the statement that gives it away.
a stack of values still waiting; the value that pops one is its answer
NEXT GREATERO(n)read it twice with i % n; only the first lap pushes
AROUND THE CIRCLEO(n)pop what today makes useless and add up what it carried
LOOKING BACKO(n)the survivors on a stack; only the top can meet the next arrival
COLLISIONSO(n)pop a bigger digit in front of a smaller one while k lasts
KEEP IT INCREASINGO(n)count each value's subarrays at the moment it is popped
EACH ELEMENT'S SHAREO(n)the bar below on the stack is the left edge, the popper the right
THE WIDEST RECTANGLEO(n)a deque falling front to back; expired indices leave the front
MONOTONIC DEQUEO(n)prefix sums in a rising deque; take from the front, prune the back
DEQUE ON PREFIX SUMSO(n)For each day, how many days ago was the price last higher than today's? Which move?
A stack of earlier prices, falling toward the top. Pop every price at most today's; the top is then the last higher one.
Maximal Rectangle asks for the largest rectangle of 1s in a 0/1 matrix. Which move does it run once per row?
Row by row, count the 1s above each cell. That row is a histogram, and unit 7 finds its largest rectangle.
dp[i] = nums[i] + the largest dp[j] among the k indices before i. Which move gives that largest value in O(1)?
The candidates form a sliding window of k values, and its maximum is the deque's front.
The scan has a while loop inside a for loop. Why is it still O(n)?
All the inner loops together pop at most as many times as the outer loop pushes: n.
None of these fail the samples. Each one fails a hidden test.
A distance, a width or a window needs positions. Push the index and read the value through it; a bare value cannot say where it was.
Next greater pops the smaller values, so the stack falls. Nearest smaller pops the larger ones, so it rises. The other test keeps exactly the values that should go.
A contribution sum stops at “smaller” on one side and “smaller or equal” on the other. Strict on both sides counts an equal pair's subarrays twice.
Values still on the stack when the scan ends are never popped, so never counted. A 0 at i = n, or a loop that drains the stack, settles them.
The front of a deque can fall out of the window. Drop it when dq.front() ≤ i − k, before reading the maximum.
A rising number such as 12345 pops nothing. The k removals are still owed and come off the end.
Nine moves on one page. The right column is the cue for each.
A value waited until something bigger popped it; a second lap went round the circle; a popped day handed over its span; survivors met at the top; a number kept its digits rising; each value counted the subarrays it was the minimum of; the bar below became a left edge; and a deque dropped the beaten at the back and the expired at the front. Maximal Rectangle (DP 4) runs unit 7 once per row, and Trapping Rain Water (module 5) has a stack solution too.
Module 13. Fifteen problems: thirteen on LeetCode, one on CSES and one on Codeforces. Next: sliding window and two pointers.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.