貪心算法
貪心的本質是：選擇每一階段的局部最優，從而達到全局最優
做題的時候，只要想清楚 局部最優 是什么，如果推導出全局最優，其實就夠了。
買賣股票的最佳實際
思路：如果第i天賣出股票，則最大利潤為(該天的股價-前面天數中最小的股價)，然后與已知的最大利潤比較，如果大于則更新當前最大利潤的值
class Solution {public int maxProfit(int[] prices) {// 初始化最大利潤為0，最低價格為第一個價格int maxProfit = 0;int minPrice = 100000;// 遍歷價格數組for (int price : prices) {// 更新最低價格minPrice = Math.min(minPrice, price);// 更新最大利潤maxProfit = Math.max(maxProfit, price - minPrice);}return maxProfit;}
}
跳躍游戲
class Solution {public boolean canJump(int[] nums) {int maxReach = 0; // 記錄能到達的最遠索引int n = nums.length;for (int i = 0; i < n; i++) {// 如果當前位置 i 已經超出最大可達范圍，則說明無法繼續前進if (i > maxReach) {return false;}// 更新最大可達范圍maxReach = Math.max(maxReach, i + nums[i]);// 如果最大可達范圍已經超過或等于最后一個索引，則返回 trueif (maxReach >= n - 1) {return true;}}return false;}
}
跳躍游戲Ⅱ
class Solution {public int jump(int[] nums) {int maxReach = 0;int current = 0;int jumps = 0;if( nums.length == 1) return 0;for(int i=0;i<nums.length-1;i++){maxReach=Math.max(i+nums[i],maxReach);if(i == current){jumps++;current = maxReach;if(current >= nums.length-1){return jumps;}}}return 0;}
}劃分字母區間
class Solution {public List<Integer> partitionLabels(String S) {char[] s = S.toCharArray();int n = s.length;int[] last = new int[26];for (int i = 0; i < n; i++) {last[s[i] - 'a'] = i; // 每個字母最后出現的下標}List<Integer> ans = new ArrayList<>();int start = 0, end = 0;for (int i = 0; i < n; i++) {end = Math.max(end, last[s[i] - 'a']); // 更新當前區間右端點的最大值if (end == i) { // 當前區間合并完畢ans.add(end - start + 1); // 區間長度加入答案start = i + 1; // 下一個區間的左端點}}return ans;}
}矩陣
堆
數組中第K個最大元素
class Solution {public int findKthLargest(int[] nums, int k) {int[] buckets = new int[20001];int n = nums.length;for(int i =0;i<n;i++){buckets[nums[i]+10000]++;}for(int i = 20000;i>=0;i--){k = k - buckets[i];if(k <= 0){return i-10000;}}return 0;}
}棧
有效括號
class Solution {public boolean isValid(String s) {//特殊情況if(s.isEmpty()){return true;}//創建棧，字符類型Stack<Character> stack = new Stack<Character>();for(char c:s.toCharArray()){if(c == '('){stack.push(')');}else if(c == '{'){stack.push('}');}else if(c=='['){stack.push(']');}// 要先判斷是否為空，再判斷出棧else if(stack.empty() || c!=stack.pop()){return false;}}if(stack.empty()){return true;}return false;}
}每日溫度
class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] result = new int[n];Stack<Integer> stack = new Stack<>(); // 單調遞減棧，存索引for (int i = 0; i < n; i++) {// 如果當前溫度比棧頂索引的溫度高，則計算等待天數while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {int prevIndex = stack.pop();result[prevIndex] = i - prevIndex;}// 當前索引入棧stack.push(i);}return result;}
}
