Monotonic Stack

单调栈，一种特殊的栈数据结构

什么是单调栈？

单调栈，是一种特殊的栈数据结构。在这种栈中，元素始终保持单调递增或单调递减的顺序。当我们插入一个新元素时，会先弹出栈顶的所有不满足单调性的元素，然后再将新元素压入栈中。

单调栈的类型

单调递增栈

栈中的每个元素比其下方的元素要大。每当新元素进栈时，如果栈顶元素比当前元素大或相等，则将栈顶元素出栈，直到栈顶元素小于新元素或栈为空。

伪代码

\begin{algorithm} \caption{Monotonic Stack for Finding the Next Greater Element} \begin{algorithmic} \Procedure{NextGreaterElement}{$nums$} \State $stack \gets \emptyset$ \Comment{Initialize an empty stack} \State $result \gets$ array of size $|nums|$ filled with $-1$ \Comment{Initialize result array with -1}

\For{$i \gets 0$ \To $|nums| - 1$}
  \While{$stack$ is not empty and $nums[stack.top()] < nums[i]$}
    \State $index \gets stack.pop()$
    \State $result[index] \gets nums[i]$
  \EndWhile
  \State $stack.push(i)$
\EndFor
\State \Return $result$

\EndProcedure
\end{algorithmic}
\end{algorithm}

Java 代码实现

import java.util.Stack;

public class MonotonicStack {
    public int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        
        // Initialize result with -1
        for (int i = 0; i < nums.length; i++) {
            result[i] = -1;
        }

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        return result;
    }

    public static void main(String[] args) {
        MonotonicStack ms = new MonotonicStack();
        int[] nums = {2, 1, 2, 4, 3};
        int[] result = ms.nextGreaterElements(nums);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

单调递减栈

栈中的每个元素比其下方的元素要小。每当新元素进栈时，如果栈顶元素比当前元素小或相等，则将栈顶元素出栈，直到栈顶元素大于新元素或栈为空。

伪代码

\begin{algorithm} \caption{Monotonic Decreasing Stack for Sliding Window Maximum} \begin{algorithmic} \Procedure{SlidingWindowMax}{$nums, k$} \State $deque \gets \emptyset$ \Comment{Initialize an empty deque} \State $result \gets$ array of size $|nums| - k + 1$

\For{$i \gets 0$ \To $|nums| - 1$}
  \Comment{Remove elements out of window}
  \If{$deque$ is not empty and $deque.front() \leq i - k$}
    \State $deque.pop\_front()$
  \EndIf

  \Comment{Maintain decreasing order in the deque}
  \While{$deque$ is not empty and $nums[deque.back()] < nums[i]$}
    \State $deque.pop\_back()$
  \EndWhile

  \State $deque.push\_back(i)$

  \Comment{Store the current window maximum}
  \If{$i \geq k - 1$}
    \State $result[i - k + 1] \gets nums[deque.front()]$
  \EndIf
\EndFor

\State \Return $result$

\EndProcedure
\end{algorithmic}
\end{algorithm}

Java 代码实现

import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMax {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // Remove elements not in the sliding window
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove elements smaller than the current number from the back
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // The front of the deque is the max element of the window
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMax swm = new SlidingWindowMax();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = swm.maxSlidingWindow(nums, k);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

单调栈的应用

• 下一个更大/更小元素：寻找某个元素右边（或左边）第一个比它大的/小的元素。例如，给定一个数组，可以利用单调栈找到每个元素的下一个更大元素。
• 滑动窗口最大值：通过单调递减栈维护滑动窗口中的最大值。
• 接雨水问题：通过单调递减栈有效地计算每个柱子之间能接多少雨水。
• 柱状图最大矩形问题：通过单调递增栈找到每个柱子能形成的最大矩形面积。

单调栈的优缺点

优点

• 高效性：单调栈可以在很多问题中将时间复杂度降低到 $O(n)$，因为每个元素只会入栈和出栈一次，这对于某些问题而言极具优势。
• 空间节省：相比于直接遍历所有可能的组合，单调栈只需要线性空间。

缺点

• 适用场景有限：单调栈主要适用于需要按顺序处理的数据，且要求能够根据当前元素的信息更新数据状态。
• 额外的空间开销：虽然相比暴力解法节省时间，但单调栈需要额外的栈空间，可能不适合内存有限的场景。