800+ IT
News
als RSS Feed abonnieren📚 Solving Monotonic Queue/Stack Problems
💡 Newskategorie: Programmierung
🔗 Quelle: dev.to
Intro
Monotonic queue and stack problems are common in competitive programming and technical interviews. These problems involve finding the shortest or longest subarray up to a certain number or looking for the distance to a greater or lesser value. In this article, we will go through various examples of monotonic queue/stack problems and demonstrate how to solve them in Java.
Basic Example: Daily Temperatures
The dailyTemperatures method calculates the number of days it would take for the temperature to rise. It maintains a decreasing stack to store the indices. When an element breaks the decreasing order, it calculates the number of days between the current and previous index.
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: Longest Well-Performing Interval
The longestWPI method finds the longest well-performing interval in an array of hours worked. It uses a decreasing stack and a prefix sum to calculate the 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: Shortest Subarray with Sum at Least K
The shortestSubarray method calculates the shortest subarray with a sum at least K. It maintains an increasing queue to store the indices.
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: Maximum Sliding Window
The maxSlidingWindow method calculates the maximum element in a sliding window of size k. It maintains a decreasing queue to store the indices, ensuring that the first element is always the maximum.
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: Sum of Subarray Minimums
The sumSubarrayMins method calculates the sum of subarray minimums. It maintains a stack to store the indices and keeps track of the previous and next lesser elements for each index.
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;
}
Conclusion
Monotonic queue and stack problems can be effectively tackled using the concepts demonstrated in the examples above. By maintaining a decreasing or increasing stack or queue, we can efficiently solve problems related to shortest or longest subarrays, distance to greater or lesser values, and more.
...