今日題目：
- Problem 1: 棧的應用
- 155. 最小棧 | LeetCode
- 20. 有效的括號 | LeetCode
- 150. 逆波蘭表達式求值 | LeetCode
- Problem 2: 單調棧
- 496. 下一個更大元素 I
- 739. 每日溫度
- 503. 下一個更大元素 II
目錄
- Problem 1：棧 - “先進后出”的應用
- LC 155. 最小棧 【easy】
- LC 20. 有效的括號 【easy】
- LC 150. 逆波蘭表達式求值 【easy】
- Problem 2：單調棧 【必會】
- ?? 單調棧解決的基本問題：找下一個更大元素 【classic】
- LC 496. 下一個更大元素 I
- LC 739. 每日溫度
- LC 503. 下一個更大元素 II 【稍有難度】
- 單調棧問題總結
今天主要學習了棧的一些應用和單調棧。
- 棧的基本應用已經學習過很多次了，像括號匹配等問題，比較熟悉了，所以難度不大。
- 單調棧比較重要，它解決了“尋找每個元素的下一個更大元素”這個基本問題。我們要學會解決這個基本問題的代碼思路，并將其通過轉化來解決具體問題。
所以，單調棧是今天的重點，要學會其解決“尋找下一個更大元素”這個基本問題的思路，再學習如何將其用于解決具體問題。
Problem 1：棧 - “先進后出”的應用
LC 155. 最小棧 【easy】
155. 最小棧 | LeetCode
這個題目做過多次了，難度不大。
LC 20. 有效的括號 【easy】
20. 有效的括號 | LeetCode
括號匹配是使用棧解決的經典問題。通過這個題，可以學會如何靈活運用 stack 來解決這個問題。
LC 150. 逆波蘭表達式求值 【easy】
150. 逆波蘭表達式求值 | LeetCode
也是一個棧的經典應用，難度不大（也可能是寫過好幾次了）。
Problem 2：單調棧 【必會】
單調棧用于解決找下一個更大元素的問題。這是 LeetCode 中一類經典問題。學會的話就不難，沒學的話一時也不太好想到思路。
首先需要學會使用單調棧的基本模板，然后再學習如何利用它解決具體的問題。
?? 單調棧解決的基本問題：找下一個更大元素 【classic】
參考 單調棧結構解決三道算法題 | labuladong
首先明確單調棧所能解決的基本問題：給一個數組 A，找出其中每個元素的右邊的下一個更大元素。比如 A = [5, 1, 7]，那么結果就是 answer = [7, 7, -1]，因為 5 和 1 的下一個更大元素都是 7，而 7 沒有下一個更大元素，于是填充 -1 作為特殊值。當然，answer 中的值也可以是 A 的下標索引，這樣就是 answer = [2, 2, -1]，因為 A[0] 和 A[1] 的下一個更大元素的索引都是 2，所以 answer[0] 和 answer[1] 都是 2。
解決的思想是，假設每個元素的值就是這個元素的身高，讓每個元素向后看，比自己矮的都身高不夠，而第一個露出頭來比自己高的那個元素就是答案，比如下圖：
圖片來自 labuladong
那尋找 answer 的方法，從代碼上實現思路就是：聲明一個 stack，從后向前遍歷 nums，每次元素入棧前，把棧頂上擠壓掉身高小于等于自己的元素，然后記錄下棧頂（也就是 nums[i] 身后更大的元素），接著入棧，繼續下一輪循環，直到遍歷 nums 結束。代碼如下：
int[] findNextLarger(int[] nums) {int[] nextLarger = new int[nums.length]; // 存放 answerList<Integer> stack = new ArrayList<>(); // 單調棧// 從后向前遍歷 numsfor (int i = nums.length - 1; i >= 0; i--) {// 擠壓掉身高小于等于自己的元素while (!stack.isEmpty() && stack.getLast() <= nums[i]) {stack.removeLast();}// 記錄棧頂元素作為 nums[i] 身后的更大元素nextLarger[i] = stack.isEmpty()? -1: stack.getLast();// 入棧nextLarger.addLast(nums[i]);} return nextLarger;
}
這個問題中，每個元素都被 push 一次，最多被 pop 一次，所以復雜度是 O ( n ) O(n) O(n)。
有了解決這個基本問題的代碼模板，我們就可以用這個單調棧的思路來解決一些具體的問題了。
LC 496. 下一個更大元素 I
496. 下一個更大元素 I | LeetCode
學會了上面的基本代碼模板，解決這個問題就會容易很多了。
這個題目的特殊之處在于，我們需要找 nums2 的子集 nums1 在 nums2 中的下一個更大元素，所以我們對 nums2 使用之前的方法來得到 nextLarger 數組，然后需要再將其轉換為 map，記錄著 元素 -> 下一個更大元素 的映射，然后 nums1 就可以使用這個 map 進行檢索從而得到答案。
代碼如下圖：
可以看出來，解決這個問題的關鍵還是使用單調棧。
LC 739. 每日溫度
739. 每日溫度 | LeetCode
這也是對基本問題的一個變形，我們再 nextLarger 中需要存的不是下一個更大的元素，而是下一個更大元素的索引下標，這樣才能計算出索引下標的差值。學會基本問題之后，難度也不大。
LC 503. 下一個更大元素 II 【稍有難度】
503. 下一個更大元素 II | LeetCode
這也是一個基本問題的變形，基本問題中，nums 是一個普通數組，而這個題將 nums 定義為一種環形數組。
面對這種需求，常用套路就是將數組長度翻倍：
實現這種“翻倍”的效果的方式，可以構造新數組、可以利用循環數組的技巧（取模）、可以兩次循環等等，都可以。
單調棧問題總結
我們學會了單調棧解決“下一個更大元素”這個基本問題的解題方法，但在實際應用中，題目往往會更加復雜一些，這時我們需要把具體問題轉化為單調棧相關問題來解決。
