Basic example:
Trying to keep stack decreasing. If it's increasing we can say that current index - previous index would give us number of days in between.
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[T.length];
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[stack.peek()] < T[i]) {
int prev = stack.pop();
res[prev] = i - prev;
}
stack.push(i);
}
return res;
}
Decreasing stack with prefix sum:
Using prefix sum and trying to keep stack decreasing. When we're going from right side we know that last value in the stack is the smallest. Checking sum and updating result.
public int longestWPI(int[] hours, int K) {
int len = hours.length;
int[] preSum = new int[len+1]; // prefix Sum
for (int i = 1; i <= len; i++) {
preSum[i] = preSum[i-1] + (hours[i-1] > 8 ? 1 : -1);
}
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i <= len; i++) {
//building decreasing stack
if (stack.isEmpty() || preSum[stack.peek()] > preSum[i]) {
stack.push(i);
}
}
int res = 0;
// going from right side
for (int j = len; j >= 0; j--) {
//if summ difference is greater or equals K
// sum of values between two pointers >= K
while (!stack.isEmpty() && preSum[stack.peek()] + K <= preSum[j]) {
res = Math.max(res, j-stack.pop());
}
}
return res;
}
Queue shortest subarray:
Since we're looking for shortest we're trying to maintain queue increasing and poll all values that are greater than current.
public int shortestSubarray(int[] A, int K) {
int n = A.length + 1;
int[] preSum = new int[n];
for (int i = 1; i < n; i++) {
preSum[i] = A[i - 1] + preSum[i - 1]; // presum[0] = 0
}
//keep deque increasing
Deque<Integer> deque = new ArrayDeque<>();
int result = n;
for (int i = 0; i < n; i++) {
//if presum decreasing poll last
while (!deque.isEmpty() && preSum[i] <= preSum[deque.peekLast()]) {
deque.pollLast();
}
//if diff >= k calculate result
while (!deque.isEmpty() && preSum[i] - preSum[deque.peekFirst()] >= K) {
result = Math.min(result, i - deque.pollFirst());
}
deque.addLast(i);
}
return result == n ? -1 : result;
}
Window monotonic queue:
Trying to keep queue always decreasing, so first element is max.
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
ArrayDeque<Integer> queue = new ArrayDeque<>();
int j = 0;
for (int i = 0; i < k; i++) {
// we pop last if sequence increasing and find proper position
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.addLast(i);
}
for (int i = k; i < n; i++) {
// we keep first element as max
res[j++] = nums[queue.peekFirst()];
// we check if queue first is out of window we discard it
while (!queue.isEmpty() && queue.peekFirst() < i - k + 1) {
queue.pollFirst();
}
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.addLast(i);
}
res[j] = nums[queue.peekFirst()];
return res;
}
Maintaining previous less element and next less elements:
public int sumSubarrayMins(int[] A) {
int n = A.length;
int sum = 0;
Stack<Integer> stack = new Stack<>();
int[] prev = new int[n];
int[] next = new int[n];
Arrays.fill(next, n);
Arrays.fill(prev, -1);
for(int i = 0; i < A.length; i++) {
while(!stack.isEmpty() && A[stack.peek()] > A[i]) {
int prevIndex = stack.pop();
next[prevIndex] = i;
}
if (!stack.isEmpty()) {
prev[i] = stack.peek();
}
stack.add(i);
}
for(int i = 0; i < n; i++) {
int left = i - prev[i];
int right = next[i] - i;
int subarraysBtw = (left * right) % mod;
sum += (A[i] * subarraysBtw) % mod;
sum %= mod;
}
return sum;
}