棧 · 深入學習

## 棧特點：后進先出（LIFO）出棧入棧都是O(1)內完成可以用一個單鏈表來實現 ## leet-code練手 ### 20. 有效的括號 ~~~ package com.mango.leet.code.simple; /** * 20. 有效的括號 */ import java.util.Stack; /** * 給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串 s ，判斷字符串是否有效。 * * 有效字符串需滿足： * * 左括號必須用相同類型的右括號閉合。 * 左括號必須以正確的順序閉合。 * ? * * 示例 1： * * 輸入：s = "()" * 輸出：true * 示例?2： * * 輸入：s = "()[]{}" * 輸出：true * 示例?3： * * 輸入：s = "(]" * 輸出：false * 示例?4： * * 輸入：s = "([)]" * 輸出：false * 示例?5： * * 輸入：s = "{[]}" * 輸出：true * ? * * 提示： * * 1 <= s.length <= 104 * s 僅由括號 '()[]{}' 組成 * * 來源：力扣（LeetCode） * 鏈接：https://leetcode-cn.com/problems/valid-parentheses * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */ public class LC20 { public static void main(String[] args) { System.out.println((int)'('); System.out.println((int)')'); System.out.println((int)'{'); System.out.println((int)'}'); System.out.println((int)'['); System.out.println((int)']'); System.out.println(new Solution().isValid("(){}}{")); } static class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack(); for(int i=0;i<s.length();i++){ if(stack.isEmpty()){ stack.push(s.charAt(i)); continue; } char c = s.charAt(i); Character character = stack.pop(); if(character == ']' || character == '}' || character == ')'){ return false; } if((character == '[' && c == ']') || (character == '{' && c == '}') || (character == '(' && c == ')')){ // 括號匹配，并且左括號在前 }else{ stack.push(character); stack.push(c); } } return stack.isEmpty(); } public boolean isValid2(String s) { Stack<Character> stack = new Stack(); for(int i=0;i<s.length();i++){ char c = s.charAt(i); if(c == '['){ stack.push(']'); }else if(c == '{'){ stack.push('}'); }else if(c == '('){ stack.push(')'); }else if(!stack.isEmpty() && c != stack.peek()){ return false; }else { stack.pop(); } } return stack.isEmpty(); } // 自己用數組加下標模擬棧，不用api public boolean isValid3(String s) { int l = s.length(); char []st = new char[l]; int top = -1; for(int i = 0;i < l;i++){ char s_in = s.charAt(i); if(s_in == '(' || s_in == '[' || s_in == '{'){ top++; st[top] = s_in; } else{ if(top < 0){ return false; } if(s_in == ')' && st[top] != '('){ return false; } if(s_in == ']' && st[top] != '['){ return false; } if(s_in == '}' && st[top] != '{'){ return false; } top--; } } if(top > -1){ return false; } return true; } } } /** * 2022-03-02 * 思路： * 利用棧先入后出的特點，如果括號匹配就出站，不匹配且做括號在前的就先入棧 */ ~~~ #### 739每日溫度 ~~~ package com.mango.leet.code.middle; /** * 739. 每日溫度 */ import java.util.Arrays; import java.util.Stack; /** * 給定一個整數數組?temperatures?，表示每天的溫度，返回一個數組?answer?，其中?answer[i]?是指在第 i 天之后，才會有更高的溫度。如果氣溫在這之后都不會升高，請在該位置用?0 來代替。 * * ? * * 示例 1: * * 輸入: temperatures = [73,74,75,71,69,72,76,73] * 輸出:?[1,1,4,2,1,1,0,0] * 示例 2: * * 輸入: temperatures = [30,40,50,60] * 輸出:?[1,1,1,0] * 示例 3: * * 輸入: temperatures = [30,60,90] * 輸出: [1,1,0] * ? * * 提示： * * 1 <=?temperatures.length <= 105 * 30 <=?temperatures[i]?<= 100 * * 來源：力扣（LeetCode） * 鏈接：https://leetcode-cn.com/problems/daily-temperatures * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */ public class LC739 { public static void main(String[] args) { int[] arr = new int[]{89,62,70,58,47,47,46,76,100,70}; System.out.println(Arrays.toString(new Solution().dailyTemperatures(arr))); } static class Solution { // [73,74,75,71,69,72,76,73] public int[] dailyTemperatures(int[] temperatures) { int[] result = new int[temperatures.length]; Stack<Integer> stack = new Stack<Integer>(); for(int i=0;i<temperatures.length;i++){ while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){ int index = stack.pop(); result[index] = i - index; } stack.push(i); } return result; } } } /** * 2022-03-03 * 思路： * 1. 將下標壓入棧里 * 2. 遍歷比較當前下標數據A和棧內下標數據B，如果A>B,則出棧并記錄站內下標的變暖天數，并將A下標壓入站內 * 3. 遍歷站內數據和當前下標數據做對比，重復步驟2 * 4. 如果棧空或者當前值小于站內下標對應值，則入棧 */ ~~~