LeetCodeHot100

LeetCodeHot100_0x09

70. 最小棧·數據結構實現

求解思路： 一開始想著只用一個最小棧結構不就實現了，結果測試的時候發現，在pop元素后，它的最小值有可能不受影響，但是只用一個最小棧的話，最小值一定是作為棧頂元素最先被彈出了。而且題目要求彈出的元素是指按順序插入的元素。因此原數據的插入順序也需要用一個棧保存。也就是說，這題用兩個Deque結構分別存儲所有元素和維護當前元素存入時最小值的棧。

另外我看到評論區有老哥分享字節一面的進階要求——不使用額外空間完成。

class MinStack {public Deque<Integer> stack;    // 保存所有元素public Deque<Integer> minStack; // 保存最小值的順序// 初始化函數public MinStack() {stack = new LinkedList<Integer>();minStack = new LinkedList<Integer>();}// 推入堆棧public void push(int val) {// 普通棧直接插入stack.push(val);// 最小棧考慮插入if(minStack.isEmpty()) {minStack.push(val);}else {int topNum = minStack.peek();if(val < topNum) {minStack.push(val);}else {// 確保元素個數與普通棧相等，并可以很好反映每個元素插入時的當前最小值情況minStack.push(minStack.peek()); }}}// 刪除棧頂元素public void pop() {// push保證了，所以兩個一起刪除就行stack.pop();minStack.pop();}// 獲取棧頂元素public int top() {// 這個獲取的是普通棧的棧頂return stack.peek();}// 常數時間（棧頂）public int getMin() {// 這個獲取的是最小棧的棧頂return minStack.peek();}
}

71. 字符串解碼

求解思路： 同樣使用棧進行處理，這題的難點更多在于字符串的操作，主要需要判斷四類東西：

遇到數字（注意可能有多位）：
遇到左括號：入隊
遇到右括號：出隊
遇到字符：加入到當前需要處理的字符串中

class Solution {public String decodeString(String s) {Deque<Integer> numStack = new ArrayDeque<>();       // 存儲處理的次數Deque<StringBuilder> strStack = new LinkedList<>(); // 存儲每一輪需要處理字符串StringBuilder res = new StringBuilder();  // 存儲答案int num = 0; // 處理次數// 轉成字符數組處理for(char c : s.toCharArray()) { //1. 判斷是否為十進制數字if(Character.isDigit(c)) { // 整數的取值范圍1--300，所以需要進行 num * 10num = num * 10 + (c - '0');  }//2. 判斷碰到左括號else if(c == '[') {// 把本輪操作次數入棧numStack.push(num);  strStack.push(res);res = new StringBuilder();num = 0;   }//3. 判斷碰到右括號，就需要將本輪的字符串和需要處理的次數取出來進行處理else if(c == ']') { // 保存原字符串StringBuilder currStr = res;// 取出本輪字符串res = strStack.pop();// 取出本輪處理次數int cnt = numStack.pop();for(int i=0;i<cnt;i++) {// 累加到答案中res.append(currStr);}}//4. 如果不是特殊符號，而是字符，那就加入到本輪字符串中else {res.append(c);}}return res.toString();}
}

72. 每日溫度

求解思路： 暴力法找思路、優化暴力算法得到的逆向跳躍法可以解決問題。
【暴力大王】看看暴力能怎么優化

class Solution {public int[] dailyTemperatures(int[] temperatures) {// answer[i] 表示對于第i天，后面幾天會出現更高溫度// 先試試暴力解法int n = temperatures.length;int [] ans = new int[n];for(int i=0;i<n;i++) {int j;for(j=i+1;j<n;j++) {if(temperatures[j] > temperatures[i]) {ans[i] = j-i;break;}}if(j == n)ans[i] = 0;}return ans;}
}

【暴力優化——逆向跳躍法】將遍歷順序變成逆向的，這樣可以優先處理出后面可復用的ans數組。

定義j從距離i最近的位置開始探測
如果當前探測位置j 存在 t[j] > t[i] ，探測結束直接更新 ans[i] = j-i;
如果當前探測位置j 的ans = 0，表明后面沒有比t[j]更大的了,又由于當前t[j] <= t[i],所以 ans[i] = 0
如果當前探測位置j的ans != 0，為了提高探測效率，可以直接越過那些小于t[j]的位置，直接來到j + ans[j]的位置進行繼續探測

class Solution {public int[] dailyTemperatures(int[] temperatures) {// 暴力優化——逆序跳躍法int n = temperatures.length;int[] ans = new int[n];// 因為是找后面有沒有更大的，所以用倒過來處理的方法for(int i=n-2;i>=0;i--) {  // 從最接近i的位置開始探測 int j = i + 1;while(true) {//1.如果探測到當前位置大于i，保存答案 if(temperatures[j] > temperatures[i]) {ans[i] = j - i;break;}//2. 如果探測到當前位置ans數組為0，//   說明比t[j]大的不存在，并且由于t[i] > t[j],所以ans[i]也為0else if(ans[j] == 0) {ans[i] = 0;break;}//3. 走到這說明t[i] >= t[j] && ans[j] != 0// 也就是說，在j往后ans[j]的位置上 首次存在一個大于t[j]的值// 由于當前t[j] 小于 t[i], 只有大于t[j]的才有可能大于t[i]// 所以j 可以直接跳躍到 j + ans[j] 的位置上else {j += ans[j];    // 直接跳到比res[j]大的位置繼續探測}}}return ans;}
}

73. 柱狀圖中最大的矩形（不會）

求解思路： 借著官解的圖來看，我們首先要確定這道題它計算機是如何觸發面積計算的。

當我們遍歷過程中，第一輪遍歷到2，將它作為矩形高度的話，我們繼續往后遍歷，直到遍歷到1，發現此時小于高度2了，那就觸發當前面積計算，高度h = 2，寬度w = 右邊界 - 左邊界 = 2 - 0 = 2。
再來，如果以5作為矩形高度呢?向右遍歷到6，比5大，繼續遍歷；遍歷到2，比5小，開始觸發面積計算。
再來，如果以6作為矩形高度呢?注意我們不僅僅要考慮后面未遍歷的高度，也要留意前面已經遍歷了的高度。以6作為矩形高度，向右遍歷到2，觸發面積計算，此時左邊界是元素5的下標，右邊界是元素2的下標

總結：

計算機如何計算每個高度的面積呢？通過維護左右邊界，左邊出現第一個小于它的，右邊出現第一個小于它的，這兩個值的差作為該矩形的有效寬度，而有效高度就是當前高度。
如何觸發計算呢? 以當前高度所在下標開始向后遍歷，找到第一個小于它的觸發面積計算？
如何快速保存上一個邊界值的有效高度呢？可以通過棧來維護單調性

【哨兵單調棧】之所以加兩個哨兵，前哨兵是為了避免空棧，后哨兵強制觸發剩余元素的面積更新。

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;// 在原數組首尾各添加一個0作為哨兵// 首哨兵：arr[0] = 0; 避免空棧檢查// 尾哨兵：arr[n+1] = 0；強制剩余元素出棧計算面積int[] arr = new int[n + 2]; System.arraycopy(heights,0,arr,1,n); // 從heights[0] 開始依次拷貝到arr，拷貝n個元素// 棧的作用：存儲柱子的下標，確保棧內對應高度是單調遞增的Deque<Integer> stack = new LinkedList<>();stack.push(0);      // 左哨兵int maxArea = 0;    // 記錄最大面積for(int i=1;i<arr.length;i++) {// 維護單調遞增棧// 如果當前柱子高度小于棧頂對應高度時，觸發面積計算while(arr[i] < arr[stack.peek()]) {int h = arr[stack.pop()];       // 獲取當前棧頂的有效長度// 彈出完棧頂高度后，當前的stack.peek()是左邊界下標// 當前 i 是右邊界下標int width = i - stack.peek()-1; // 計算有效寬度maxArea = Math.max(maxArea, h * width);}// 壓入當前下標，繼續維護高度遞增特性stack.push(i);}return maxArea;}
}

74. 數組中第k個最大元素

求解思路： 考察數據結構的選型，要求第k個大的數，可以用大小為k的最小堆來解決。遍歷元素一遍，最后堆頂就是第k大的數。

class Solution {public int findKthLargest(int[] nums, int k) {// 利用大小為k的小堆解決，遍歷完之后堆頂就是第k大的元素PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);for(int i=0;i<k;i++) {minQueue.offer(nums[i]);}for(int i=k;i<nums.length;i++) {if(nums[i] > minQueue.peek()) { // 大于當前最小，最小彈出，他加入minQueue.poll();minQueue.offer(nums[i]);}}return minQueue.peek();}
}

75. 前K個高頻元素

求解思路： 前k個高頻元素，首先我們得統計出每個元素的頻數，這里可以使用哈希結構進行統計。統計完之后，我們遍歷哈希的key列表，并用大小為k的小根堆進行維護，最后倒序輸出小根堆的值就行了。
【哈希 + 小根堆】

class Solution {public int[] topKFrequent(int[] nums, int k) {// hashMap統計 + 小根堆維護Map<Integer,Integer> hm = new HashMap<>();for(int num : nums ) {hm.put(num,hm.getOrDefault(num,0) + 1);}// 特殊情況，k>= hm.size()if(k >= hm.size()) {return hm.keySet().stream().mapToInt(i->i).toArray();}// 小根堆維護PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> hm.get(a) - hm.get(b));for(int num : hm.keySet()) {heap.offer(num);if(heap.size() > k) {heap.poll();}}// 提取答案int[] res = new int[k];for(int i=0;i<k;i++) {res[i] = heap.poll();}return res;}
}

76. 數據流的中位數

求解思路： 這題我看了題解理解之后才寫出來的，根本還是對數據結構的理解不到位。如果能想到用優先隊列，這題其實很好做。
首先，定義兩個優先隊列，分別動態維護前半區元素和后半區元素，兩者的堆頂極有可能產生中位數。存儲前半區元素的堆采用最大堆，存儲后半區元素的堆采用最小堆。在進行添加元素操作時，遵循以下判定步驟：

1. 首先判斷該元素應該添加到前半區還是后半區 ---> 前半區為空 或者 當前元素小于前半區堆頂元素
2.  判斷堆頂元素需不需要遷移

class MedianFinder {PriorityQueue<Integer> queMin; // 最大堆，保存較小的一半元素。堆頂是這一半中的最大值。PriorityQueue<Integer> queMax; // 最小堆，保存較大的一半元素。堆頂是這一半的最小值public MedianFinder() { // 初始化大頂堆和小頂堆queMin = new PriorityQueue<Integer>((a,b) -> (b-a));queMax = new PriorityQueue<>((a,b) -> (a-b));}public void addNum(int num) {// 前一半是空 | 當前元素小于堆頂元素// 將當前元素加入queMin，然后判斷數量，是否需要堆頂遷移if(queMin.isEmpty() || num < queMin.peek()) {queMin.offer(num); // 如果說queMin - queMax >=2，為保證平衡，需要將queMin堆頂遷移加入到queMaxif(queMax.size() + 1 < queMin.size()) {queMax.offer(queMin.poll());}}else { // 反之加入后半區queMax.offer(num);// 同理判斷后半區堆頂是否需要遷移if(queMax.size() > queMin.size()) {queMin.offer(queMax.poll());}}}public double findMedian() {// 如果左半區多，證明是奇數，堆頂為中位數// 否則是偶數，取兩個堆頂的中間值if(queMin.size() > queMax.size()) {return queMin.peek();}return (queMin.peek() + queMax.peek()) / 2.0;}
}

77. 買賣股票的最佳時機

求解思路： 因為只能買賣一次，所以用兩個變量遍歷更新就行了。記錄最小值min_profit，然后判斷當前遍歷到的元素中，是否存在利潤大于max_profit，大于就進行更新。

class Solution {public int maxProfit(int[] prices) {int max_profit = 0;int min_profit = Integer.MAX_VALUE;for(int i=0;i<prices.length;i++) {if(prices[i] < min_profit) {min_profit = prices[i];}else if(prices[i] - min_profit > max_profit) {max_profit = prices[i] - min_profit;}}return max_profit;}
}

78.跳躍游戲

求解思路： 遍歷數組的時候更新當前可達的最遠距離。如果在遍歷過程中發現當前位置比當前最遠距離還大則說明不可達。

class Solution {public boolean canJump(int[] nums) {int n = nums.length;int k = 0;for(int i=0;i<n;i++) {// 如果當前點的距離比前面所能到達的最大距離還要大，則說明當前位置不可達if(i > k) return false;k = Math.max(k,i + nums[i]);}return true;}
}

79. 跳躍游戲Ⅱ

求解思路： 在上一題的基礎上，對于每一次跳躍次數，都記錄對應的最遠跳躍距離，然后下一輪遍歷中，在可達的位置中繼續尋找下一次跳躍次數可以跳躍的最遠距離。當更新到最遠距離可達最后一位時，此時記錄的跳躍次數就是最小跳躍次數。

class Solution {public int jump(int[] nums) {int n = nums.length;int ans = 0;int start = 0;int end = 1;while(end < n) {int maxDis = 0;for(int i=start ;i<end; i++) {// 能跳到的最遠的距離maxDis = Math.max(maxDis, i+nums[i]);}start = end; // 下一次跳躍，可以選擇的跳躍范圍end = maxDis + 1; // 下一次跳躍最遠的跳躍距離ans++;      // 計入跳躍次數}return ans;}
}

80. 劃分字母區間

求解思路： 這題模擬一下案例就能大概清楚更新策略。只是策略優化的問題。
【策略一】

首先最簡單的想法，雙指針st和ed，st指第一個字母，然后ed指最后一個字母。每一輪st，ed都去找對于st字母最后的位置，然后更新長度currlen，直到某一次st == currlen 時，說明前面的字母都匹配了。可以以 0 - 0 + currlen作為一個劃分區間。
但是這個策略很容易退化成O(n^2)，因為做了無用功，對于重復的字母，我們重復進行了ed指針移動尋找的操作，實際上，我們可以實現預處理出26個字母對應的最后的位置。這樣更簡單。也就是下面的終極版策略二：哈希 + 雙指針 + 貪心

【哈希 + 雙指針 + 貪心】

class Solution {public List<Integer> partitionLabels(String s) {// 一個比較好的想法// 首先預處理出每個字母的最后一個位置的下標是什么int len = s.length();int[] last = new int[26];for(int i=0;i<len;i++) {last[s.charAt(i) - 'a'] = i; // 處理每個字母的下標是什么}List<Integer> ans = new ArrayList<>();int st = 0, end = 0;for(int i=0;i<s.length();i++) {// 這里的思路是貪心，首先需要分割的長度是動態變化的// 具體的，例如ababcc，一開始i指向第一個a，end記錄2// i++指向b，end更新到3// i++指向a，end不變// i++指向b，end不變，此時 i == end，說明之前的字母都匹配要求了，直接切割end = Math.max(end,last[s.charAt(i)-'a']);  // 這一步十分關鍵if(i == end) {ans.add(end - st + 1); // 記錄長度st = end + 1; // 更新起始點}}return ans;}
}