栈
有效的括号
20. 有效的括号 - 力扣（LeetCode）
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
示例 5：
输入：s = "([)]"
输出：false
解法及思路
栈
遇到左括号入栈，遇到右括号检查栈顶是否匹配。
1. 遍历字符串 2. 遇到左括号：入栈 3. 遇到右括号： - 栈为空 → false - 栈顶不匹配 → false - 匹配 → 弹出栈顶 4. 遍历结束，栈为空 → true
输入："{[]}"
遍历： '{' → 入栈 → stack=['{'] '[' → 入栈 → stack=['{', '['] ']' → 栈顶是'['，匹配 → 弹出 → stack=['{'] '}' → 栈顶是'{'，匹配 → 弹出 → stack=[] '}' → 字符串遍历完 栈为空 → true ✅输入："([)]"
遍历： '(' → 入栈 → stack=['('] '[' → 入栈 → stack=['(', '['] ')' → 栈顶是'['，不匹配 → false ❌ 结果：falseclass Solution { public boolean isValid(String s) { Deque<Character> stack=new ArrayDeque<>(); for(char c:s.toCharArray()){ if(c=='('){ stack.push(')'); }else if(c=='['){ stack.push(']'); }else if(c=='{'){ stack.push('}'); }else{ if(stack.isEmpty()||stack.pop()!=c){ return false; } } } return stack.isEmpty(); } }最小栈
155. 最小栈 - 力扣（LeetCode）
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
实现MinStack类:
MinStack()初始化堆栈对象。void push(int value)将元素value推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]解释：MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.解法及思路
辅助栈
用一个辅助栈记录每个位置的最小值。
主栈：存储所有元素 辅助栈：存储对应位置的最小值 push时： 主栈入栈 辅助栈入 min(当前元素, 辅助栈栈顶) pop时： 两个栈都弹出 getMin时： 返回辅助栈栈顶
操作序列：push(-2), push(0), push(-3)
push(-2): 主栈：[-2] 辅助栈：[-2] ← 最小值-2 push(0): 主栈：[-2, 0] 辅助栈：[-2, -2] ← min(0, -2) = -2 push(-3): 主栈：[-2, 0, -3] 辅助栈：[-2, -2, -3] ← min(-3, -2) = -3 getMin() → 辅助栈栈顶 = -3 ✅ pop(): 主栈：[-2, 0] 辅助栈：[-2, -2] top() → 主栈栈顶 = 0 ✅ getMin() → 辅助栈栈顶 = -2 ✅
class MinStack { private Deque<Integer> stack; private Deque<Integer> minstack; public MinStack() { stack=new ArrayDeque<>(); minstack=new ArrayDeque<>(); } public void push(int value) { stack.push(value); //辅助入栈min if(minstack.isEmpty()){ minstack.push(value); }else{ int minval=Math.min(minstack.peek(),value); minstack.push(minval); } } public void pop() { stack.pop(); minstack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minstack.peek(); } }贪心算法
买股票的最佳时机
121. 买卖股票的最佳时机 - 力扣（LeetCode）
给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
示例 1：
输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。解法及思路
一次遍历
遍历价格，记录"历史最低价"，计算"当前卖出"的利润，更新最大利润。
1. 记录历史最低价 minPrice 2. 对于每天的价格： - 计算利润 = 当前价格 - minPrice - 更新最大利润 - 更新 minPrice = min(minPrice, 当前价格)
prices = [7, 1, 5, 3, 6, 4]
第1天：price=7 minPrice = 7 maxProfit = 0 第2天：price=1 profit = 1 - 7 = -6（不买） minPrice = min(7, 1) = 1 maxProfit = 0 第3天：price=5 profit = 5 - 1 = 4 maxProfit = max(0, 4) = 4 minPrice = min(1, 5) = 1 第4天：price=3 profit = 3 - 1 = 2 maxProfit = max(4, 2) = 4 第5天：price=6 profit = 6 - 1 = 5 maxProfit = max(4, 5) = 5 minPrice = min(1, 6) = 1 第6天：price=4 profit = 4 - 1 = 3 maxProfit = max(5, 3) = 5 结果：5 ✅
class Solution { public int maxProfit(int[] prices) { int minprice=Integer.MAX_VALUE; int maxprofit=0; for(int i=0;i<prices.length;i++){ if(prices[i]<minprice){ minprice=prices[i];//更新最小价格 }else if(prices[i]-minprice>maxprofit){ maxprofit=prices[i]-minprice;//更新最大利润 } } return maxprofit; } }跳跃游戏
55. 跳跃游戏 - 力扣（LeetCode）
给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。
示例 1：
输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：
输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。解法及思路
贪心
维护"能到达的最远位置"，遍历数组，更新最远位置。
1. 初始化 maxReach = 0（能到达的最远位置） 2. 遍历数组： - 如果 i > maxReach，说明当前位置不可达，返回false - 更新 maxReach = max(maxReach, i + nums[i]) - 如果 maxReach >= n-1，返回true 3. 遍历结束，返回true
nums = [2,3,1,1,4]
初始：maxReach = 0 i=0: nums[0]=2 i=0 <= maxReach=0 ✅ maxReach = max(0, 0+2) = 2 2 < 4，继续 i=1: nums[1]=3 i=1 <= maxReach=2 ✅ maxReach = max(2, 1+3) = 4 4 >= 4 → 返回true ✅
nums = [3,2,1,0,4]
初始：maxReach = 0 i=0: nums[0]=3 maxReach = max(0, 0+3) = 3 i=1: nums[1]=2 maxReach = max(3, 1+2) = 3 i=2: nums[2]=1 maxReach = max(3, 2+1) = 3 i=3: nums[3]=0 maxReach = max(3, 3+0) = 3 i=4: nums[4]=4 i=4 > maxReach=3 ❌ 不可达 → 返回false
class Solution { public boolean canJump(int[] nums) { int maxreach=0; for(int i=0;i<nums.length;i++){ if(i>maxreach) return false; maxreach=Math.max(maxreach,i+nums[i]); if(i+nums[i]>=nums.length-1){ return true; } } return false; } }动态规划
爬楼梯
70. 爬楼梯 - 力扣（LeetCode）
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2输出：2解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：
输入：n = 3输出：3解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶解法及思路
动态规划
到达第 n 阶，可以从第 n-1 阶爬1步，或从第 n-2 阶爬2步。
dp[n] = dp[n-1] + dp[n-2] dp[1] = 1 dp[2] = 2
n = 5
dp[1] = 1（1种：1） dp[2] = 2（2种：1+1, 2） dp[3] = dp[2] + dp[1] = 2 + 1 = 3 dp[4] = dp[3] + dp[2] = 3 + 2 = 5 dp[5] = dp[4] + dp[3] = 5 + 3 = 8
示意图：
n=1: 1 n=2: 2 n=3: 3 n=4: 5 n=5: 8
就是斐波那契数列
class Solution { public int climbStairs(int n) { if(n<=2) return n; int[] dp=new int[n+1]; dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; } }打家劫舍
198. 打家劫舍 - 力扣（LeetCode）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。解法及思路
动态规划
对于第 i 间房，有两种选择：
1. 偷第 i 间：金额 = dp[i-2] + nums[i] 2. 不偷第 i 间：金额 = dp[i-1] 取最大值
状态转移方程：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
nums = [2, 7, 9, 3, 1]
dp[0] = 2（只有1间房，偷） dp[1] = max(2, 7) = 7（偷7） dp[2] = max(7, 2+9) = max(7, 11) = 11（偷2和9） dp[3] = max(11, 7+3) = max(11, 10) = 11（不偷3） dp[4] = max(11, 11+1) = max(11, 12) = 12（偷2,9,1） 结果：12 ✅
class Solution { public int rob(int[] nums) { if(nums.length==0) return 0; if(nums.length==1) return nums[0]; int[] dp=new int[nums.length]; dp[0]=nums[0]; dp[1]=Math.max(nums[0],nums[1]); for(int i=2;i<nums.length;i++){ //选和不选 dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]); } return dp[nums.length-1]; } }零钱兑换
322. 零钱兑换 - 力扣（LeetCode）
给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11输出：3解释：11 = 5 + 5 + 1示例 2：
输入：coins = [2], amount = 3输出：-1示例 3：
输入：coins = [1], amount = 0输出：0解法及思路
动态规划
dp[i] 表示凑成金额 i 所需的最少硬币数。
dp[i] = min(dp[i - coin]) + 1 （对所有 coin） dp[0] = 0
解释：
凑成金额 i，可以选一枚硬币 coin 然后凑成 i - coin 所以 dp[i] = dp[i - coin] + 1 取所有 coin 中最小的
coins = [1, 2, 5], amount = 11
dp[0] = 0 dp[1] = min(dp[0]+1) = 1 dp[2] = min(dp[1]+1, dp[0]+1) = min(2, 1) = 1 dp[3] = min(dp[2]+1, dp[1]+1) = min(2, 2) = 2 dp[4] = min(dp[3]+1, dp[2]+1) = min(3, 2) = 2 dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = min(3, 3, 1) = 1 ... dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3, 3, 3) = 3
结果：3 ✅
class Solution { public int coinChange(int[] coins, int amount) { int[] dp=new int[amount+1]; Arrays.fill(dp,amount+1); dp[0]=0; for(int i=1;i<=amount;i++){ for(int coin:coins){ if(coin<=i){ dp[i]=Math.min(dp[i-coin]+1,dp[i]); } } } return dp[amount]>amount?-1:dp[amount]; } }单词拆分
139. 单词拆分 - 力扣（LeetCode）
给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入:s = "leetcode", wordDict = ["leet", "code"]输出:true解释:返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
输入:s = "applepenapple", wordDict = ["apple", "pen"]输出:true解释:返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。示例 3：
输入:s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出:false解法及思路
动态规划
dp[i] 表示 s 的前 i 个字符能否被拆分。
dp[i] = true 表示 s[0..i-1] 可以被拆分 dp[0] = true（空字符串可以被拆分） 对于每个 i，遍历 j < i： 如果 dp[j] == true 且 s[j..i-1] 在字典中 则 dp[i] = true
s = "leetcode", wordDict = ["leet", "code"]
dp[0] = true（空串） i=1: s[0..0]="l"，不在字典 → dp[1]=false i=2: s[0..1]="le"，不在字典 → dp[2]=false i=3: s[0..2]="lee"，不在字典 → dp[3]=false i=4: s[0..3]="leet"，在字典 → dp[4]=true i=5: 检查j=0..4 j=0: dp[0]=true, s[0..4]="leetc"，不在字典 j=1: dp[1]=false j=2: dp[2]=false j=3: dp[3]=false j=4: dp[4]=true, s[4..4]="c"，不在字典 → dp[5]=false i=6: 检查j=0..5 j=4: dp[4]=true, s[4..5]="co"，不在字典 → dp[6]=false i=7: 检查j=0..6 j=4: dp[4]=true, s[4..6]="cod"，不在字典 → dp[7]=false i=8: 检查j=0..7 j=4: dp[4]=true, s[4..7]="code"，在字典 → dp[8]=true 结果：dp[8]=true ✅
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> set=new HashSet<>(wordDict); boolean[] dp=new boolean[s.length()+1]; dp[0]=true; for(int i=1;i<=s.length();i++){ for(int j=0;j<i;j++){ if(dp[j]&&set.contains(s.substring(j,i))){ dp[i]=true; break; } } } return dp[s.length()]; } }最长递增子序列
300. 最长递增子序列 - 力扣（LeetCode）
给你一个整数数组nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3]输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]输出：1解法及思路
动态规划
dp[i] = 以 nums[i] 结尾的最长递增子序列长度。
对于每个 i，遍历 j < i： 如果 nums[j] < nums[i] 则 dp[i] = max(dp[i], dp[j] + 1)
nums = [10, 9, 2, 5, 3, 7, 101, 18]
dp[0] = 1（10） dp[1] = 1（9，前面没有比9小的） dp[2] = 1（2） dp[3] = 2（2,5） dp[4] = 2（2,3） dp[5] = 3（2,3,7） dp[6] = 4（2,3,7,101） dp[7] = 4（2,3,7,18） 结果：4 ✅
class Solution { public int lengthOfLIS(int[] nums) { int[] dp=new int[nums.length]; Arrays.fill(dp, 1); int maxlen=1; for(int i=1;i<nums.length;i++){ for(int j=0;j<i;j++){ if(nums[j]<nums[i]){ dp[i]=Math.max(dp[i],dp[j]+1); } } maxlen=Math.max(maxlen,dp[i]); } return maxlen; } }
