Java 單調棧：從入門到實戰

引言

在 Java 編程中，數據結構的選擇和使用往往是解決復雜問題的關鍵。單調棧（Monotonic Stack）作為一種高效的數據結構，能夠在 O(n) 時間復雜度內解決許多與單調性相關的問題，例如“下一個更大元素”、“股票價格跨度”等。對于 CSDN 的讀者來說，深入理解單調棧不僅能提升代碼能力，還能在面試和項目中脫穎而出。本文將帶你從單調棧的基本概念入手，逐步深入到 Java 實現與實戰應用，附上詳細代碼示例，讓你輕松掌握這一利器！

---

什么是單調棧？

單調棧是一種特殊的棧結構，其核心在于保持棧內元素的單調性，即從棧底到棧頂元素要么單調遞增，要么單調遞減。在操作時，單調棧會通過彈出不符合單調性的元素來維持這一特性，從而在處理實時單調性問題時表現出色。

單調遞增棧

• 定義：棧內元素從棧底到棧頂單調遞增。
• 入棧規則：當新元素入棧時，如果棧頂元素大于或等于新元素，則不斷彈出棧頂元素，直到棧頂小于新元素或棧為空。

單調遞減棧

• 定義：棧內元素從棧底到棧頂單調遞減。
• 入棧規則：當新元素入棧時，如果棧頂元素小于或等于新元素，則不斷彈出棧頂元素，直到棧頂大于新元素或棧為空。

單調棧的這種動態調整機制，使其在特定場景下非常高效。

---

單調棧的應用場景

單調棧在算法和實際項目中有廣泛應用，以下是幾個經典場景：

1. 下一個更大元素（Next Greater Element）：在數組中為每個元素找到右邊第一個比它大的元素。
2. 股票價格跨度（Stock Span Problem）：計算連續天數中股票價格不高于當天的最大天數。
3. 直方圖中最大矩形（Largest Rectangle in Histogram）：在直方圖中找到面積最大的矩形。
4. 溫度預測：在溫度數組中找到每個溫度下一次更高溫度出現的日子。

這些問題有一個共同點：需要快速找到某種單調關系，而單調棧正是解決這類問題的“殺手锏”。

---

Java 實現單調棧

在 Java 中，我們可以利用 java.util.Stack 類來實現單調棧。下面以“下一個更大元素”問題為例，展示單調遞減棧的實現。

代碼示例：下一個更大元素

import java.util.Stack;public class MonotonicStackExample {public static int[] nextGreaterElement(int[] nums) {int n = nums.length;int[] result = new int[n];Stack<Integer> stack = new Stack<>(); // 單調遞減棧// 從右向左遍歷數組for (int i = n - 1; i >= 0; i--) {// 彈出所有小于當前元素的棧內元素while (!stack.isEmpty() && stack.peek() <= nums[i]) {stack.pop();}// 如果棧不為空，棧頂即為下一個更大元素，否則為 -1result[i] = stack.isEmpty() ? -1 : stack.peek();// 當前元素入棧stack.push(nums[i]);}return result;}public static void main(String[] args) {int[] nums = {2, 1, 2, 4, 3};int[] result = nextGreaterElement(nums);for (int num : result) {System.out.print(num + " "); // 輸出: 4 2 4 -1 -1}}
}

代碼解析

• 棧的單調性：棧內元素保持單調遞減。
• 遍歷方向：從右向左遍歷，便于找到右側的更大元素。
• 邏輯：
  1. 對于當前元素 nums[i]，彈出棧內所有小于等于它的元素。
  2. 若棧為空，則右側無更大元素，記為 -1；否則棧頂即為答案。
  3. 將當前元素壓入棧，繼續處理下一個元素。

---

單調棧的優勢

1. 時間復雜度：每個元素最多入棧和出棧一次，總時間復雜度為 O(n)。
2. 空間復雜度：最壞情況下棧存儲所有元素，空間復雜度為 O(n)。
3. 實時性：單調棧適合動態數據流場景，能實時維護單調性。

---

實戰應用：股票價格跨度

問題描述：給定一個股票價格數組，計算每一天股票價格不高于當天的連續天數（包括當天）。

解法：使用單調遞增棧，棧內存儲價格及其對應的跨度，動態累加跨度。

代碼示例

import java.util.Stack;public class StockSpan {public static int[] stockSpan(int[] prices) {int n = prices.length;int[] spans = new int[n];Stack<int[]> stack = new Stack<>(); // 存儲 [價格, 跨度]for (int i = 0; i < n; i++) {int span = 1;// 彈出棧內小于等于當前價格的元素，累加其跨度while (!stack.isEmpty() && stack.peek()[0] <= prices[i]) {span += stack.pop()[1];}spans[i] = span;stack.push(new int[]{prices[i], span});}return spans;}public static void main(String[] args) {int[] prices = {100, 80, 60, 70, 60, 75, 85};int[] spans = stockSpan(prices);for (int span : spans) {System.out.print(span + " "); // 輸出: 1 1 1 2 1 4 6}}
}

代碼解析

• 棧的單調性：棧內價格單調遞增。
• 跨度計算：當遇到更高價格時，彈出棧內較小的價格并累加其跨度。
• 結果：spans[i] 表示第 i 天對應的跨度。

---

總結

單調棧憑借其高效性和簡潔性，成為解決單調性問題的利器。本文從概念到代碼，詳細介紹了 Java 中單調棧的實現與應用，涵蓋了“下一個更大元素”和“股票價格跨度”兩個經典案例。無論你是準備算法面試，還是在項目中優化代碼，單調棧都值得你深入掌握。

希望這篇博客能為你帶來啟發！如果有疑問或想了解更多應用場景，歡迎在評論區留言交流。

參考資料

• LeetCode: Next Greater Element
• GeeksforGeeks: Stock Span Problem

---

希望這篇博客能幫你在面試或項目中游刃有余！有疑問歡迎留言討論，喜歡請點贊關注哦！