算法篇之單調棧

單調棧算法入門

單調棧是一種特殊的數據結構應用，它的核心在于維護一個棧，使得棧內元素保持單調遞增或者單調遞減的順序。這種數據結構在解決很多算法問題時非常有效，例如求數組中每個元素的下一個更大元素、每日溫度問題等。

一、單調棧的基本概念

單調棧有兩種類型：

單調遞增棧：棧中元素從棧底到棧頂是遞增的
單調遞減棧：棧中元素從棧底到棧頂是遞減的

兩種方法實現起來沒有太大區別，單調棧的核心在于維護一個元素單調增單調減的順序，一般實現都是將數組值或數組對應索引存到棧中，使得該數組元素或索引對應的元素在棧中保持單調性。以單調遞增舉例，一旦遇到比棧頂元素小的元素便彈出棧頂元素，然后將該元素壓入棧中。這是一般單調棧題目的最常用做法

二.單調棧的基本思路

確定單調性：根據問題需求決定使用遞增棧還是遞減棧
- 找下一個更大元素 → 遞減棧
- 找下一個更小元素 → 遞增棧
存儲內容：
- 可以存儲元素值
- 也可以存儲元素索引（當需要計算距離或位置時）
遍歷方向：
- 可以從左到右遍歷
- 也可以從右到左遍歷（根據問題需求）
邊界處理：
- 注意處理棧為空的情況
- 注意處理遍歷完成后棧中剩余元素

三、單調棧的基本實現

以存儲數組元素為例，簡單看一下單調棧的實現

import java.util.Deque;
import java.util.LinkedList;public class MonotonicStack {// 單調遞增棧示例public static void increasingStack(int[] nums) {Deque<Integer> stack = new LinkedList<>();for (int num : nums) {// 當棧不為空且當前元素小于棧頂元素時，彈出棧頂元素while (!stack.isEmpty() && num < stack.peek()) {System.out.println(stack.pop() + " -> " + num);}stack.push(num);}// 處理棧中剩余元素（沒有下一個更小元素）while (!stack.isEmpty()) {System.out.println(stack.pop() + " -> -1");}}// 單調遞減棧示例public static void decreasingStack(int[] nums) {Deque<Integer> stack = new LinkedList<>();for (int num : nums) {// 當棧不為空且當前元素大于棧頂元素時，彈出棧頂元素while (!stack.isEmpty() && num > stack.peek()) {System.out.println(stack.pop() + " -> " + num);}stack.push(num);}// 處理棧中剩余元素（沒有下一個更大元素）while (!stack.isEmpty()) {System.out.println(stack.pop() + " -> -1");}}public static void main(String[] args) {int[] nums = {3, 1, 4, 2, 5};System.out.println("單調遞增棧結果:");increasingStack(nums);System.out.println("\n單調遞減棧結果:");decreasingStack(nums);}
}

四、單調棧的典型應用

1. 力扣496.下一個更大的元素I

題目描述：nums1 中數字 x 的 下一個更大元素 是指 x 在 nums2 中對應位置右側的 第一個 比 x 大的元素。

給你兩個 沒有重復元素 的數組 nums1 和 nums2 ，下標從 0 開始計數，其中nums1 是 nums2 的子集。

對于每個 0 <= i < nums1.length ，找出滿足 nums1[i] == nums2[j] 的下標 j ，并且在 nums2 確定 nums2[j] 的 下一個更大元素 。如果不存在下一個更大元素，那么本次查詢的答案是 -1 。

返回一個長度為 nums1.length 的數組 ans 作為答案，滿足 ans[i] 是如上所述的 下一個更大元素 。

示例 1：

輸入：nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出：[-1,3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：
- 4 ，用加粗斜體標識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
- 1 ，用加粗斜體標識，nums2 = [1,3,4,2]。下一個更大元素是 3 。
- 2 ，用加粗斜體標識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {HashMap<Integer, Integer> hs = new HashMap<>();int[] res = new int[nums1.length];Deque<Integer> stack = new LinkedList<>();Arrays.fill(res, -1);for (int i = 0; i < nums1.length; i++) {hs.put(nums1[i], i);}stack.push(0);for (int i = 1; i < nums2.length; i++) {if (nums2[i] > nums2[stack.peek()]) {while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {if (hs.containsKey(nums2[stack.peek()])) {res[hs.get(nums2[stack.peek()])] = nums2[i];}stack.pop();}}stack.push(i);}return res;}
}

2. 力扣739.每日溫度

題目描述：給定一個整數數組 temperatures ，表示每天的溫度，返回一個數組 answer ，其中 answer[i] 是指對于第 i 天，下一個更高溫度出現在幾天后。如果氣溫在這之后都不會升高，請在該位置用 0 來代替。

示例 1:

輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出: [1,1,4,2,1,1,0,0]

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < temperatures.length; i++) {if (temperatures[i] > temperatures[stack.peek()]) {while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {res[stack.peek()] = i - stack.peek();stack.pop();}stack.push(i);} else {stack.push(i);}}return res;}
}