-
-
- 代碼随想錄一刷個人記錄
-
- 2022/7/14（leetcode）
- 2022/7/15（leetcode）
- 2022/7/17【字元串】
- 2022/7/18【字元串】
- 2022/7/20【雙指針】
- 2022/7/21【棧 / 隊列】
- 2022/7/22【棧 / 隊列】
- 2022/7/23【二叉樹】
- 2022/7/24【二叉樹】
- 2022/7/25【二叉樹】
- 2022/7/26【二叉樹】
- 2022/7/28【二叉樹】
- 2022/7/29【二叉樹】
- 2022/7/30【二叉樹】
- 2022/7/31【二叉樹】
- 2022/8/1【二叉樹】
- 2022/8/2【二叉樹】
- 2022/8/3【回溯】
- 2022/8/4【回溯】
- 2022/8/5【回溯】
- 2022/8/6【回溯】
- 2022/8/7【回溯】
- 2022/8/8【回溯】
- 貪心：
- 2022/8/9【貪心】
- 2022/8/10【貪心】
- 2022/8/11【貪心】
- 2022/8/12【貪心】
- 2022/8/14【貪心】
- 2022/8/15【貪心】
- 2022/8/16【貪心】
- 2022/8/18【貪心】
- 動态規劃步驟：
- 2022/8/19【動态規劃】
- 2022/8/20【動态規劃】
- 2022/8/21【動态規劃】
- 2022/8/22【動态規劃：0-1背包】
- 2022/8/23【動态規劃】
- 2022/8/24【動态規劃：完全背包】
- 2022/8/25【動态規劃：完全背包】
- 2022/8/26【動态規劃：完全背包】
- 2022/8/27【動态規劃：多重背包、打家劫舍系列】
- 2022/8/28【動态規劃：買賣股票的最佳時機系列】
- 2022/8/29【動态規劃：買賣股票的最佳時機系列】
- 2022/8/30【動态規劃：買賣股票的最佳時機系列】
- 2022/9/1【動态規劃：子序列系列】
- 2022/9/2【動态規劃：子序列系列】
- 2022/9/3【動态規劃：子序列系列】
- 2022/9/4【動态規劃：子序列系列】
- 2022/9/5【動态規劃：子序列系列】
- 2022/9/6【動态規劃：子序列系列】
- 2022/9/7【動态規劃：子序列系列】
- 單調棧：
- 2022/9/8【單調棧】
- 2022/9/9【單調棧】
- 2022/9/10【接雨水補充】
- 2022/9/11【柱狀圖中最大的矩形】
- 額外題目：
- 2022/9/12【額外題目：數組】
- 2022/9/13【額外題目：數組】
- 2022/9/15【額外題目：數組】
- 2022/9/16【額外題目：反轉字元串相關】
- 要點注意：
-
代碼随想錄一刷個人記錄
2022/7/14（leetcode）
- 在排序數組中查找元素的第一個和最後一個位置（34）【二分查找，分别查找左右邊界】
- 有效的完全平方數（367）【二分查找】
- 比較含倒退的字元串（844）【逆序雙指針】
- 有序數組的平方（977）【雙指針】
- 長度最小的子數組（209）【滑動視窗（雙指針）】
- 水果成籃（904）【滑動視窗】
- 最小覆寫子串（76）【滑動視窗，困難】
- 螺旋矩陣 II（59）【設定上下左右邊界】
- 螺旋矩陣（54）【設定上下左右邊界，更容易了解】
2022/7/15（leetcode）
- 移除連結清單元素（203）
- 設計連結清單（707）
- 删除連結清單的倒數第 N 個結點（19）【嘗試使用虛拟節點】
- 環形連結清單 II（142）【數學推導】
-
環形連結清單（141）【數學推導】
===============================
- 有效的字母異位詞（242）【額外數組】
- 贖金信（383）【和上題一樣的思路】
- 字母異位詞分組（49）【字母異位詞排序後的結果是一樣的】
-
兩個數組的交集（349）【容器可以使用别的容器的疊代器進行初始化】
================================
- 找到字元串中所有字母異位詞（438）【滑動視窗，按照模闆寫】
-
字元串的排列（567）【滑動視窗，按照模闆寫】
================================
- 兩個數組的交集 （349）【hashset】
- 兩個數組的交集 II（350）【hashmap】
- 四數相加 II（454）【hashmap】
-
兩數之和（1）【hashset】
================================
- 三數之和（15）【雙指針，去重，剪枝】
- 四樹之和（18）【雙指針，去重，剪枝】
2022/7/17【字元串】
- 反轉字元串（344）
- 反轉字元串II（541）
- 替換空格（5）【注意周遊時的邊界判斷】
- 翻轉字元串裡的單詞（151）【整體反轉 + 去除空格（雙指針，考慮前後空格） + 部分反轉】
- 左旋轉字元串（劍指58）
2022/7/18【字元串】
-
實作 strStr()（28）【KMP算法】
時間複雜度分析：
1、周遊過程：雖然在比對失敗的時候，next指針會回退，但回退的次數跟之前比對成功的次數相關（也就是查找數組指針右移的次數），
而數組指針右移的次數不會超過n，是以回退的次數最多也就是n，總次數2n；
2、構造next過程：如上，總次數2m。
【最壞情況例子：aaaabaaaac aaaaa】
在b比對失敗時，要回退3次
- 重複的子字元串（459）【用到KMP算法】
/*
理論：數組長度len -（next[len-1] + 1）就會得到最小的周期長度l（l != len，等于說明沒有重複子串），
如果len = n*l，則說明題目為true
*/
2022/7/20【雙指針】
- 删除有序數組中的重複項（26）
- 移動零（283）
- 比較含倒退的字元串（844）【！！！每個字元串回退到真正需要比較的字元】
- 有序數組的平方（977）【必須使用額外數組】
-
三數之和/四數之和（15/18）
【1. 先排序 2. 剪枝：要注意target為任意值的判斷條件 3. 雙指針 4. 去重】
2022/7/21【棧 / 隊列】
基礎理論：棧和隊列都是容器擴充卡，底層可以使用不同容器實作（預設使用deque），是以元素在記憶體中的資料分布取決于底層容器。
- 用隊列實作棧（225）【實際隻需要一個隊列就可以實作】
- 有效的括号（20）
- 删除字元串中的所有相鄰重複項（1047）
- 逆波蘭表達式求值（150）
2022/7/22【棧 / 隊列】
- 滑動視窗最大值（239）
- 前 K 個高頻元素（347）【排序使用包含k個的小頂堆，優化時間複雜度至O(nlogk)，注意堆的構造寫法（包含容器和比較方式）】
2022/7/23【二叉樹】
基礎理論：數節點的代碼編寫；深度優先周遊（利用棧，無論是遞歸還是疊代），廣度優先周遊（利用隊列）
- 前序周遊（144）【注意疊代版的插入節點順序】
- 中序周遊（94）【和其他兩個不同】
- 後序周遊（145）【可通過修改前序周遊，最後反轉結果得到】
2022/7/24【二叉樹】
【層次周遊】
- 二叉樹的層序周遊（102）
- 二叉樹的層序周遊 II（107）
- 二叉樹的右視圖（199）
- 二叉樹的層平均值（637）
- N 叉樹的層序周遊（429）
- 在每個樹行中找最大值（515）
- 填充每個節點的下一個右側節點指針（116）
- 填充每個節點的下一個右側節點指針 II（117）【普通二叉樹，對于層次周遊沒有差別】
- 二叉樹的最大深度（104）【疊代法】
- 二叉樹的最小深度（111）【疊代法，遞歸法也要注意】
2022/7/25【二叉樹】
- 翻轉二叉樹（226）【遞歸、疊代：前序】
- N 叉樹的前序周遊（589）
- N 叉樹的後序周遊（590）
2022/7/26【二叉樹】
- 對稱二叉樹（101）【遞歸：前序；疊代：前序、層次】
- 二叉樹的最大深度（104）
- 二叉樹的最小深度（111）【要注意疊代法（後序周遊）】
2022/7/28【二叉樹】
- 完全二叉樹的節點個數（222）【注意是完全二叉樹，要用到對應的性質減少複雜度】
- 二叉樹的所有路徑（257）【回溯思想、疊代】
- 相同的樹（100）【遞歸：前序；疊代：前序、層次】
- 另一棵樹的子樹（572）【遞歸：在100的基礎上，在主函數判斷子樹部分】
2022/7/29【二叉樹】
- 平衡二叉樹（110）【遞歸：後續周遊】
- 左葉子之和（404）【遞歸：後序；疊代：前序 / 後序】
- 找樹左下角的值（513）【遞歸：有回溯思想（需要變量記錄最大深度和值）；疊代：層次】
- 路徑總和（112）【遞歸；疊代】【計算路徑總和要先減去目前節點值】
- 路徑總和 II（113）【遞歸：回溯】
2022/7/30【二叉樹】
- 從中序與後序周遊序列構造二叉樹（106）【遞歸：數組分割，下标處理】
- 從前序與中序周遊序列構造二叉樹（105）
- 最大二叉樹（654）【和上面類似】
- 合并二叉樹（617）【遞歸；疊代】
- 二叉搜尋樹中的搜尋（700）【遞歸；疊代；利用二叉搜尋樹的性質】
- 二叉搜尋樹的最小絕對差（530）【遞歸、疊代：中序（二叉搜尋樹中序有序），記錄前繼節點】
- 驗證二叉搜尋樹（98）【類似上面一題】
2022/7/31【二叉樹】
- 二叉搜尋樹中的衆數（501）【記錄前繼和計數，注意衆樹可能有多個】
- 二叉樹的最近公共祖先（236）【遞歸：後序，有傳回】
- 二叉搜尋樹的最近公共祖先（235）【遞歸；疊代；類似二分法】
2022/8/1【二叉樹】
- 二叉搜尋樹中的插入操作（701）【遞歸；疊代；在葉子節點處插入】
// 疊代這裡的值判斷，要加else，不然編譯器會覺得cur可能會指派兩次 // 本來是nullptr，再指派就報空指針異常 while (cur){ parent = cur; if (val < cur->val) cur = cur->left; // 這裡的else要加 else if (val > cur->val) cur = cur->right; } - 删除二叉搜尋樹中的節點（450）【遞歸；疊代；删除節點的4種情況（寫在另外一個函數中）；删除要記得要delete】
- 修剪二叉搜尋樹（669）【遞歸；疊代；注：這裡不能随便delete節點，因為不能保證另一側不為空，直接删除會導緻記憶體洩漏】
2022/8/2【二叉樹】
- 将有序數組轉換為二叉搜尋樹（108）【遞歸】
- 有序連結清單轉換二叉搜尋樹（109）【遞歸：中序周遊；指針要變化也要加&】
- 把二叉搜尋樹轉換為累加樹（538）【遞歸；疊代；反中序周遊】
2022/8/3【回溯】
- 組合（77）【有剪枝優化；需要startIndex】
2022/8/4【回溯】
- 組合總和 III（216）【剪枝優化；需要startIndex】
- 電話号碼的字母組合（17）【外層周遊給定字元串，内層是回溯】
2022/8/5【回溯】
/*
組合問題：
1、如果是一個集合來求組合的話，就需要startIndex，例如：77.組合 (opens new window)，216.組合總和III (opens new window)。
2、如果是多個集合取組合，各個集合之間互相不影響，那麼就不用startIndex，例如：17.電話号碼的字母組合
*/
- 組合總和（39）【檢查目标可以用遞減的方式；需要startIndex】
- 組合總和 II（40）【去重操作；需要startIndex】
- 分割回文串（131）【分割：要有個start參數，表示待分割字串；多一個判斷回文串函數】
- 複原 IP 位址（93）【分割：在原字元串上進行修改】
2022/8/6【回溯】
- 子集（78）【回溯：子集問題】
- 子集 II（90）【回溯：子集問題 + 去重】
- 遞增子序列（491）
2022/8/7【回溯】
- 全排列（46）【回溯：排列問題】
- 全排列 II（47）【回溯：排列問題；剪枝：要注意多加一個條件，防止樹枝剪枝】
if ( (i > 0 && nums[i] == nums[i-1] && !used[i-1]) || used[i] == true) continue;
3. 重新安排行程（332）【hard；使用回溯；難點：選擇容器】
2022/8/8【回溯】
- N 皇後（51）【hard；回溯：二維數組】
- 解數獨（37）【hard；回溯：二維遞歸（因為不知道哪些位置需要填充）】
貪心：
即每次查找局部最優，以達到全局最優
2022/8/9【貪心】
- 分發餅幹（455）【大尺寸優先滿足大胃口 or 小尺寸優先滿足小胃口】
- 擺動序列（376）【找局部峰值個數 + 1】
2022/8/10【貪心】
- 最大子數組和（53）【也可以用動态】
- 跳躍遊戲（55）【題目思想：考慮覆寫範圍，周遊覆寫下标；注意數組大小==1的情況】
- 跳躍遊戲 II（45）
2022/8/11【貪心】
- K 次取反後最大化的數組和（1005）【自定義排序函數】
- 加油站（134）【考慮不存在解的情況：統計全部耗油累加和】
- 分發糖果（135）【hard；使用兩次貪心分别比較左邊/右邊；要注意比較左/右邊的周遊順序；注意更新是利用上一個值+1，而不是自身++】
2022/8/12【貪心】
- 檸檬水找零（860）【總共三種情況，貪心針對第三種】
- 根據身高重建隊列（406）【和分發糖果（135）有類似的思想，遇到這種兩個次元的問題，一定要想如何确定一個次元，然後在按照另一個次元重新排列，不要同時考慮兩個次元】【涉及要點3、4】
2022/8/14【貪心】
- 用最少數量的箭引爆氣球（452）【其實就是**求有幾個非重疊區域**】
-
無重疊區間（435）
【這兩道題思路類似，隻是在傳回結果不同；
容易了解的兩種方法
（每次拿左邊界和記錄的右邊界比較，判斷是否在一個區域）
- 按照起始位置排序，然後從左往右周遊（同一個重疊區域内需要更新最小的右邊界）
- 按照結束位置排序，然後從左往右周遊（同一個重疊區域内不需要更新右邊界，因為目前右邊界一定是這個區域最小的）】
2022/8/15【貪心】
- 劃分字母區間（763）【不是貪心，也不用回溯；學習思想：如何把同一個字母的都圈在同一個區間裡】
-
合并區間（56）
【和射氣球（452）不同；
射氣球是找一個重疊區間内都要有重疊部分，是以找***最小右邊界***；
這個問題是找最大右邊界，和其中一個有重疊關系即可】
【比如：[1, 4], [2, 7], [6, 8]
① 射氣球：[1, 4]和[2, 7]重疊
② 合并區間：[1, 4], [2, 7], [6, 8]重疊
2022/8/16【貪心】
- 單調遞增的數字（738）【思路學習，注意–操作和指派9操作要分開，不然100會得到90，而不是99】
2022/8/18【貪心】
- 監控二叉樹（968）【hard；為了更少的攝像頭，需要優先在葉子節點的父節點設定；從下往上周遊：後序；為每個節點設定3種狀态；最後還要考慮頭節點可能沒覆寫到的情況】
動态規劃步驟：
- 确定**dp數組**（dp table）以及下标的含義
- 确定遞推公式
- dp數組如何初始化
- 确定**周遊順序**
- 舉例推導dp數組
2022/8/19【動态規劃】
-
斐波那契數（509）
【使用遞歸的時間、空間複雜度分析】斐波那契遞歸算法的複雜度
- 爬樓梯（70）【題目說明n是一個正整數，是以讨論dp[0]沒有意義，直接從1開始】
2022/8/20【動态規劃】
- 使用最小花費爬樓梯（746）
- 不同路徑（62）
- 不同路徑 II（63）
2022/8/21【動态規劃】
- 整數拆分（343）【内循環：周遊拆分的可能 j，然後計算dp[i]】
- 不同的二叉搜尋樹（96）【内循環：周遊作為頭節點的可能 j】
2022/8/22【動态規劃：0-1背包】
- 0-1背包問題
- 二維數組：
- dp數組：dp[i][j] 表示從下标為[0-i]的物品裡任意取，放進容量為j的背包，價值總和最大是多少
- 遞推公式：
- 不放物品i：由dp[i - 1][j]推出，即背包容量為j，裡面不放物品i的最大價值，此時dp[i][j]就是dp[i - 1][j]。(其實就是當物品i的重量大于背包j的重量時，物品i無法放進背包中，是以被背包内的價值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時候不放物品i的最大價值，那麼dp[i - 1][j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]); -
初始化：
dp數組第一行dp[0][j]，其他為0
-
周遊順序：
雙層循環：先周遊物品（dp數組的行），再**從小到大**周遊重量（dp數組的列）【周遊順序可以颠倒】
- 滾動數組（一維）
- dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]
- 遞推公式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); -
初始化：
dp[0] = 0，
其他：如果題目給的**價值都是正整數那麼非0下标都初始化為0就可以了，如果題目給的價值有負數，那麼非0下标就要初始化為負無窮**。
-
周遊順序：
必須先周遊物品，再周遊重量【周遊順序不能颠倒】；
同時周遊重量時，要從大到小【倒序周遊的原因是：本質上還是一個對二維數組的周遊，并且右下角的值依賴上一層左上角的值，是以需要保證左邊的值仍然是上一層的，從右向左覆寫。】
【從小到大周遊會使一件物品重複取多次】
舉一個例子：【物品0的重量weight[0] = 1，價值value[0] = 15
如果正序周遊
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此時dp[2]就已經是30了，意味着物品0，被放入了兩次，是以不能正序周遊。】
- 二維數組：
- 分割等和子集（416）【使用回溯逾時，轉換為背包問題，注意dp數組的大小】
-
最後一塊石頭的重量 II（1049）【和上題類似，隻是最後傳回處理不一樣；分成盡量相等重量的兩堆，然後兩堆相撞，而不是一對一對相撞，要集體看】
【注意：上面兩題重量和價值都是一樣的】
2022/8/23【動态規劃】
- 目标和（494）
- 轉換成背包問題（01背包的**求組和問題**）：
要整體看，将數組整體分為兩部分，加法的總和為 x，減法的總和則為 sum - x x - (sum - x) = target -> x = (sum + target) / 2 問題轉換成求組合為 x 的背包問題 // 還要擔心 / 2 向下取整會不會影響，以及求出的x < 0 的可能 // target也可能是負數 if (abs(target) > sum) return 0; if ((target + sum) % 2) return 0; int bagSize = (target + sum) / 2; if (bagSize < 0) return 0; - dp數組定義：
- dp[j] 表示：填滿j（包括j）這麼大容積的包，有dp[j]種方法（求的是裝滿背包有幾種方法（組合問題），和之前不一樣）
- 遞推公式：
dp[j] += dp[j-nums[i]]; // 記住 - 初始化
dp[0] = 1; // 其他為0
- 轉換成背包問題（01背包的**求組和問題**）：
- 一和零（474）【本質：兩個次元的01背包】
2022/8/24【動态規劃：完全背包】
- 完全背包（每件物品數量無限）
- 周遊順序（與01背包的差別）：
- 無論是二維數組還是一維數組，周遊順序都可以颠倒；
- 同時周遊重量時，要從小到大，這樣才能一件物品取多次。
- 周遊順序（與01背包的差別）：
-
零錢兌換 II（518）
（完全背包的求組合問題）
- 遞推公式：
dp[j] += dp[j-nums[i]]; // 記住 -
周遊順序：
求組合問題的完全背包就不能颠倒周遊順序【必須先周遊物品，再周遊重量】
如果**順序颠倒，則求的是排列問題**。
假設：coins[0] = 1，coins[1] = 5。
- 先周遊物品，再周遊重量：就是先把1加入計算，然後再把5加入計算，得到的方法數量隻有{1, 5}這種情況。而不會出現{5, 1}的情況；
- 順序颠倒：背包容量的每一個值，都要經過 1 和 5 的計算，就會包含了{1, 5} 和 {5, 1}兩種情況。此時dp[j]裡算出來的就是排列數！
- 遞推公式：
-
組合總和 Ⅳ（377）
完全背包的排列問題：先周遊重量，再周遊物品
【注意：】
- 如果排列/組合問題隻求排列/組合數，則用動态規劃；
- 如果要把排列/組合結果都列出來，則用回溯。
2022/8/25【動态規劃：完全背包】
-
爬樓梯（70）
【擴充：一步一個台階，兩個台階，三個台階，…，直到 m個台階。
問有多少種不同的方法可以爬到樓頂呢？】
可以了解為這是一個完全背包的排列問題（1，2和2，1是不一樣的）
需要先周遊target，再周遊物品
-
零錢兌換（322）
【一般的完全背包問題，但是求最小；
這個時候要注意初始化以及範圍溢出問題；
由于是求最小，則其他的初始化應為INT_MAX*，同時要注意遞推公式裡的加法溢出問題】
-
完全平方數（279）
和零錢兌換（322）基本一樣
2022/8/26【動态規劃：完全背包】
1. 單詞拆分（139）
- 完全背包問題：**<u>周遊順序</u>**先周遊target，再**<u>周遊物品</u>**比較好了解（因為感覺不是在周遊物品，是在周遊分割字串的起始位置）；颠倒的也寫了。
- 注意：用到了**<u>unordered_set</u>**存放字元串，友善查找。
- 時間複雜度：O(n^3)，分割字串substr函數的事件複雜度是O(n)，相當于三層循環
- 空間複雜度：O(n)
2022/8/27【動态規劃：多重背包、打家劫舍系列】
- 多重背包
- 多重背包：在01背包的基礎上，使每件物品的數量不等（了解）
- 把每件有多個的物品展開，其實就是01背包問題
代碼随想錄一刷個人記錄
- 打家劫舍（198）【一般的動态規劃】
- 打家劫舍 II（213）
- 把數組分成兩部分考慮，就變成一般的198問題
- 在動态規劃部分：要考慮start == end的情況
- 打家劫舍 III（337）
- 二叉樹的周遊結合動态規劃
2022/8/28【動态規劃：買賣股票的最佳時機系列】
- 買賣股票的最佳時機（121，隻能買賣一次）
- 貪心：計算出最左的最小值，同時計算間隔
- 動态規劃：
- dp數組（二維）
- dp[i][0]：第 i 天不持有股票得到的最大金額
-
如果不是第i天賣出，則 = dp[i-1][0]
【昨天不持有，保持昨天的金額】
- 如果是第i天賣出，則 = dp[i-1][1] + prices[i]
- dp[i][0] = max (dp[i-1][0], dp[i-1][1] + prices[i])
-
- dp[i][1]：第 i 天持有股票得到的最大金額
-
如果不是第i天買入，則 = dp[i-1][1]
【昨天持有，保持昨天的金額】
- 如果是第i天買入，則 = -prices[i]
- dp[i][0] = max (dp[i-1][1], -prices[i])
-
- 最後傳回dp[i][0]，因為不持有股票的金額肯定 > 持有股票的金額
- dp[i][0]：第 i 天不持有股票得到的最大金額
- 滾動數組（一維）
- dp[0]：不持有股票得到的最大金額
- dp[1]：持有股票得到的最大金額
- dp數組（二維）
- 買賣股票的最佳時機 II（122，可以買賣多次）
- 和 121 的唯一差別
- dp[i][1]：第 i 天**持有**股票得到的最大金額
-
如果不是第i天買入，則 = dp[i-1][1]
【昨天持有，保持昨天的金額】
- 如果是第i天買入，則 = dp[i-1][0] - prices[i]
- dp[i][0] = max (dp[i-1][1], dp[i-1][0] - prices[i])
-
- 買賣股票的最佳時機 III（123，最多買賣2次）
-
由于最多買賣2次，是以每天有5種狀态，dp數組大小 = dp[size()][5]
0：沒有操作
1：第一次買入
2：第一次賣出
3：第二次買入
4：第二次賣出
【聲明：例如1狀态，并不一定就是第i天買入，也可能是之前買入，是以今天的狀态是1】
- 遞推公式
- dp[i][0]
- dp[i][1]
-
如果不是第i天買入，則 = dp[i-1][1]
【昨天就已經買入】
- 如果是第i天買入，則 = dp[i-1][0] - prices[i]
-
- dp[i][2]
- 如果不是第i天賣出，則 = dp[i-1][2]
- 如果是第i天賣出，則 = dp[i-1][1] + prices[i]
- dp[i][3]
- 如果不是第i天買入，則 = dp[i-1][3]
- 如果是第i天買入，則 = dp[i-1][2] - prices[i]
- dp[i][4]
- 如果不是第i天賣出，則 = dp[i-1][4]
- 如果是第i天賣出，則 = dp[i-1][3] + prices[i]
-
- 每個都取最大值
- 最後傳回dp[size()-1][4]，賣兩次的金額 一定 >= 賣一次的金額？？？（因為每次都是取最大？？？）
- 初始化
- dp[0][1] = -prices[0]
- dp[0][3] = -prices[0]
- 滾動數組
- 可以使用一維數組，但是指派要使用**倒序指派**，這樣不用另外儲存之前的值。
2022/8/29【動态規劃：買賣股票的最佳時機系列】
- 買賣股票的最佳時機 IV（188，最多買賣k次）
-
最多買賣k次，類似上面的123題目，dp數組大小 = dp[size()][2*k+1]
0：沒有操作
奇：買入
偶：賣出
- 遞推公式【j 是奇數】
- dp[i][j]
-
如果不是第i天買入，則 = dp[i-1][j]
【昨天就已經買入】
- 如果是第i天買入，則 = dp[i-1][j-1] - prices[i]
-
- dp[i][j + 1] 【j +1是偶數】
- 如果不是第i天賣出，則 = dp[i-1][j+1]
- 如果是第i天賣出，則 = dp[i-1][j] + prices[i]
// 整體遞推 for (int i = 1; i < prices.size(); i++){ for (int j = 1; j < 2*k; j+=2){ // 買入 dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i]); // 賣出 dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] + prices[i]); } } - 最後傳回dp[size()-1][2*k]，最後一次賣出利潤最大
- dp[i][j]
- 初始化
- dp[0][j] = -prices[0] 【j 是奇數】
- 滾動數組
- 同樣可以使用一維數組，指派要使用**倒序指派**。
// 整體遞推 for (int i = 1; i < prices.size(); i++){ for (int j = 2*k-1; j >= 1; j-=2){ // 賣出 dp[j+1] = max(dp[j+1], dp[j] + prices[i]); // 買入 dp[j] = max(dp[j], dp[j-1] - prices[i]); } }
-
- 最佳買賣股票時機含冷凍期（309，賣出後要經過一天的冷凍期，不能操作）
- 整體分成3個狀态（也可以把持有狀态細分，分成4種狀态，取決于個人了解程度）
- dp[i][0]：（第i天）持有股票，的最大金額
- dp[i][1]：（第i天）不持有股票，之前賣出，的最大金額
- dp[i][2]：（第i天）不持有股票，今天賣出，的最大金額
- 遞推公式
- dp[i][0]：持有，分為兩種情況
- 不是今天買入，昨天持有 = dp[i-1][0]
- 今天買入（那昨天一定沒有當天賣出，不然今天會進入冷凍期） = dp[i-1][1] - prices[i]
// 取最大 dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);
- dp[i][1]：不是今天賣出，說明昨天不持有，昨天不持有分為兩種情況
- 昨天不是當天賣出（更早以前賣出） = dp[i-1][1]
- 昨天是當天賣出 = dp[i-1][2]
// 取最大 dp[i][1] = max(dp[i-1][1], dp[i-1][2]);
- dp[i][2]：是今天賣出，說明昨天持有，才能賣出
dp[i][2] = dp[i-1][0] + prices[i];
- dp[i][0]：持有，分為兩種情況
- 初始化
- dp[0][0] = - prices[0]
- dp[0][1] = 0
- dp[0][2] = 0
- 滾動數組
- 使用一個dp[2, 3]大小的數組【使用一維數組要另外儲存之前的值，和二維數組沒差】
- 遞推以及最後傳回結果時使用 % 2
- 整體分成3個狀态（也可以把持有狀态細分，分成4種狀态，取決于個人了解程度）
2022/8/30【動态規劃：買賣股票的最佳時機系列】
- 買賣股票的最佳時機含手續費（714）【在122的基礎上多加一個手續費】
2022/9/1【動态規劃：子序列系列】
- 子序列和回溯應用中的【491.遞增子序列】有點類似
- 動态規劃的子序列問題，一般隻要求輸出長度，不會要求列印出所有子序列
- 最長遞增子序列（300）
- dp[i]：表示以nums[i]為結尾的最長遞增子序列長度（是以最後的結果要額外一個變量記錄，不是dp.back()）
- 初始化：dp[i] = 1
- 遞推
- 需要周遊0 < j < i，如果滿足遞增關系，dp[i] = dp[j] + 1，同時要取最大，是以公式如下
for (int i = 1; i < nums.size(); i++) { // 周遊子序列 for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1); } // 記錄出現的最大長度 if (dp[i] > res) res = dp[i]; } return res;
- 需要周遊0 < j < i，如果滿足遞增關系，dp[i] = dp[j] + 1，同時要取最大，是以公式如下
- 最長連續遞增序列（674）
- dp[i]：表示以nums[i]為結尾的最長連續遞增子序列長度（和上一題的差别）
- 初始化：dp[i] = 1
- 遞推
- 如果滿足nums[i] > nums[i-1]，dp[i] = dp[i-1]（不需要雙層循環）
- 同時要記錄最長結果res
- 數組優化
- 優化成一個變量
- 在遞推時，如果滿足遞增關系，則 +=1；否則需要重置1
2022/9/2【動态規劃：子序列系列】
- 最長重複子數組（718）
- 描述：【給定兩個數組，求兩個數組的最長連續公共序列（要求連續）】
- dp[i][j]：表示以下标 [i-1] 為結尾的nums1子序列和以下标 [j-1] 為結尾的nums2子序列
-
【注意：是表示以i-1為結尾，這是為了遞推友善；
當然也可以表示以i為結尾，這樣就要額外初始化第一行和第一列，之後從下标1開始周遊】
- 遞推
-
if (nums1[i-1] > nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
-
- 數組優化注意（重點）
- 需要判斷是否需要倒序周遊，保證要用到的舊值不會提前改變。【特别是二維數組優化為一維數組】
- 同時在不滿足遞推條件時，要注意【重新初始化】，不然可能會保留舊值。
- 複雜度
- 時間複雜度：O(n*m)
- 空間複雜度：優化前：O(n*m)；優化後：O(m)
- 最長公共子序列（1143）
- 描述：【給定兩個數組，求它們的最長公共子序列（不要求連續）】
- dp[i][j]：表示以下标 [i-1] 為結尾的test1子序列和以下标 [j-1] 為結尾的test2子序列的最長公共子序列
- 【表示以i-1結尾的原因和上一題一樣】
- 遞推【剛開始沒了解不相等的情況】
- 如果test1[i-1] == test2[j-1]，則dp[i][j] = dp[i - 1][j - 1] + 1;
- 如果不相等，【那就看看text1[0, i - 2]與text2[0, j - 1]的最長公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長公共子序列，取最大的】【即分别忽略目前判斷的兩個字元】。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
-
if (text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
- 複雜度
- 時間複雜度：O(n*m)
- 空間複雜度：O(n*m)
- 數組優化
- 不能數組優化，從遞推公式可以看出，dp[i][j]依賴左上角、左邊和上方三個舊值。
- 本日總結
- 對于求公共序列問題，dp[i][j]的表示有小技巧，即表示以下标 i-1 / j-1 為結尾，這樣不需要額外初始化第一行和第一列，周遊友善
- 數組優化的要點注意（第一道題目裡有提及）
2022/9/3【動态規劃：子序列系列】
- 不相交的線（1035）
- 描述：【給定兩個數組，元素相同的位置進行連線，求最多不相交的連線數】
- 雖然題目描述容易看不懂，但實質是求兩個數組的最長公共子序列（就是1143題目）
- 代碼跟1143一樣
- 最大子數組和（53）
- 描述：【給定一個數組，找最大連續子序列和】
- dp[i]：包括下标 i 之前的最大連續子序列和為 dp[i]
- 題目要求連續，而dp[nums.size()-1]不一定是答案【這表示以最後一個元素為結尾的連續子序列和，】，是以需要另外一個變量記錄。
2022/9/4【動态規劃：子序列系列】
- 判斷子序列（392）
- 描述：判斷字元串s（子串）是否是字元串t（主串）的子序列【如果判斷連續子序列，就是KMP算法】
- dp[i][j]：表示以下标 [i-1] 為結尾的字元串s，在以下标 [j-1] 為結尾的字元串t，中的子序列長度【注意是長度，不是單純的true/false】
- 遞推
- 如果s[i-1] == t[j-1]，比對成功，dp[i][j] = dp[i-1][j-1] + 1;
- else，【說明主串的t[j-1]字元比對失敗，則結果就是看s[i-1]和j[i-2]的比對結果】，dp[i][j] = dp[i][j-1] 【這裡重點！！！】
-
if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = dp[i][j-1];
- 初始化
- 由遞推公式可以看出，需要初始化 d[i][0]，表示以下标 i-1 為結尾的字元串，與【空字元串】的相同子序列長度，明顯都 = 0
- 傳回： dp[s.size()][t.size()] == s.size()
- 複雜度
- 時間複雜度：O(n × m)
- 空間複雜度：O(n × m)
- 數組優化
- 從遞推公式可以看出，dp[i][j] 取決于【左上角dp[i-1][j-1]】和【左邊dp[i][j-1]】，這種情況沒有辦法壓縮二維數組。
- 但如果把整個數組轉置【即内外循環次序颠倒，外層循環是主串，内層循環是子串】，就可以進行數組優化，同時内層循環要倒序周遊。
- 不同的子序列（115）
- 描述：判斷字元串s（主串）中包含字元串t（子串）的子序列個數【不要求連續，這兩個字元串的地位和上一題相反了，注意别混淆】
- dp[i][j]：以[i-1]為結尾的s子序列中出現以[j-1]為結尾的t的個數為dp[i][j]。
- 遞推
- 如果 s[i-1] == t[j-1]，比對成功，結果分為兩部分：
- 使用 s[i-1] 比對：dp[i-1][j-1]
- 不使用 s[i-1] 比對：dp[i-1][j] 【因為前面可能已經出現過完整的子串】【這裡重點！！！】
- 例如： s：bagg 和 t：bag
- dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
- else，比對失敗，不用s[i-1]比對，dp[i][j] = dp[i-1][j];
-
// 小優化：如果查找的字元串t長度 > 比對的字元串s長度，則不用判斷，一定 = 0 if (j > i) break; if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; else dp[i][j] = dp[i-1][j];
- 如果 s[i-1] == t[j-1]，比對成功，結果分為兩部分：
- 初始化
- 從遞推公式可以看出，需要初始化 d[i][0] 和 d[0][j]
- d[i][0] 表示以 i-1 為結尾的字元串s，出現【空字元串】的個數，顯然 d[i][0] = 1
- d[0][j] 表示【空字元串】，出現以 j-1 為結尾的字元串t的個數，顯然 d[0][j] = 0
- 傳回：dp[s.size()][t.size()]
- 數組優化
- 從遞推公式可以看出，d[i][j] 取決于【左上角 d[i-][j-1]】和【上方 d[i-1][j]】，可以壓縮dp數組；
- 同時注意【小優化部分】，要設定為 continue；
- 本日總結
- 上面兩題都是比對問題，跟之前的給定兩個數組找公共有不同之處，
- 不同在于，遞推時，如果判斷比對不成功，比對問題會固定目前的子串長度，縮短主串長度【子串不能删除，主串可以删除】
- 例如：dp[i][j] = d[i-1][j]
2022/9/5【動态規劃：子序列系列】
- 兩個字元串的删除操作（583）
- 描述：給定兩個字元串，求使它們變成相同字元串的最小步數【一步 = 删除一個字元】
- 跟上面的【比對問題】不同，這個問題兩個字元串都能進行删除，和9/2最長公共子序列（1143）的遞推公式有些類似。
- 兩種思路的動态規劃：第一種【直接計算最小步數】
- dp[i][j]：以[i-1]為結尾的字元串word1，和以[j-1]位結尾的字元串word2，想要達到相等，所需要删除元素的最少次數。
- 遞推：
- 如果 word1[i-1] == word2[j-1]，比對成功，dp[i][j] = dp[i-1][j-1];
- 如果不等，分為兩部分
- 删除一個字元：min(dp[i][j-1] + 1, dp[i-1][j] + 1)
- 删除兩個字元：dp[i-1][j-1] + 2
- 取最小：dp[i][j] = min(min(dp[i][j-1] + 1, dp[i-1][j] + 1) , dp[i-1][j-1] + 2);
- 初始化
- 需要初始化 dp[i][0] 和 dp[0][j]（删除成空串）
- dp[i][0] = i
- dp[0][j] = j
- 從這裡也可以看出dp數組定義[i-1]，初始化更容易
- 傳回：dp[word1.size()][word1.size()]
- 數組優化：依賴左、左上、上，不能優化。
- 第二種【跟1143一樣，先算出最長公共子序列，然後兩個字元串長度和減去最長公共序列長度】
- dp數組定義、遞推、初始化和1143一樣
- 編輯距離（72，hard）
- 描述：給定兩個字元串，求word1變成word2所需的最小操作數（可以增、删、改）
- dp[i][j]：以[i-1]為結尾的字元串word1，和以[j-1]位結尾的字元串word2，想要達到相等，所需要的最少操作次數
- 遞推：
- 如果 word1[i-1] == word2[j-1]，比對成功，dp[i][j] = dp[i-1][j-1]; 【無操作】
- 如果不等，需要進行操作，分為三種情況
- 增（取巧）：dp[i][j-1] + 1
- 【word1增 == word2删，兩個的操作數是一樣的，因為題目隻要求傳回操作數，是以不要局限在word2不能動這種思想】
- 删：dp[i-1][j] + 1【word1删一個字元】
- 改：dp[i-1][j-1] + 1
- 取最小：min（…）
- 增（取巧）：dp[i][j-1] + 1
- 初始化：
- 需要初始化 dp[i][0] 和 dp[0][j]
- dp[i][0] = i
- dp[0][j] = j
- 傳回：dp[word1.size()][word1.size()]
- 數組優化：依賴左、左上、上，不能優化。
2022/9/6【動态規劃：子序列系列】
- 回文子串（647）【另外一道題（求最長回文字串，5）】
- 描述：求一個字元串s中回文子串的個數
- （有兩種思路）動态規劃
- dp[i][j]：表示區間範圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。
- 遞推:
- 如果s[i] != s[j]，dp[i][j] = false
- 如果相等：
- i == j，dp[i][j] = true
- j - i == 1，dp[i][j] = true
- j - i > 1，if（dp[i+1][j-1] = true），dp[i][j] = true
-
// 未簡化版本 // 沒有寫出!=的情況，因為一開始初始化就全為false if (s[i] == s[j]) { if (j - i <= 1 || dp[i+1][j-1]){ dp[i][j] = true; ++res; } // else！！！ } // else！！！ //------------------------------------------- // 簡化版本 if (s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1])) { dp[i][j] = true; ++res; } // else！！！
- 初始化：全為false
- 周遊順序：
- 從遞推公式可以看出，dp[i][j] 依賴左下角，是以要從下往上、從左往右周遊
- 數組優化（可以進行優化）注意點：
- 增加額外的初始化（因為這是一維數組，是以要有額外的初始化步驟）
- 如果使用了未簡化的版本，則需要加兩處 else（見上面代碼塊）
- 如果使用簡化版本，則隻需要加一處
- 增加額外的初始化（因為這是一維數組，是以要有額外的初始化步驟）
- 複雜度：
- 時間複雜度：O(n^2)
- 空間複雜度：優化前：O(n^2)；優化後：O(n)
- 雙指針
- 以每個元素 or 每兩個元素為中心，向外擴充
- 複雜度：
- 時間複雜度：O(n^2)
- 空間複雜度：O(1)
2022/9/7【動态規劃：子序列系列】
- 最長回文子序列（516）
- 描述：給定一個字元串，求出最長回文子序列的長度【回文子序列不要求連續！！！】
- dp[i][j]：表示字元串s在[i, j]範圍内最長的回文子序列的長度。
- 遞推：
- 如果s[i] == s[j]，dp[i][j] = dp[i+1][j-1] + 2
- 如果不等，說明兩端不能增加回文子序列的長度，那dp[i][j] = 内部的最長長度：
- dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- 初始化：
- dp[i][i] = 1
- 周遊順序：
- 從遞推公式可以看出，dp[i][j] 依賴左下角（還有下方、左邊），是以要從下往上、從左往右周遊
- 數組優化
- 不能優化，從周遊順序那一條可以看出
- 複雜度：
- 時間複雜度：O(n^2)
- 空間複雜度：優化前：O(n^2)
單調棧：
2022/9/8【單調棧】
- 什麼時候用單調棧
- 通常是一維數組，要尋找任一個元素的右邊或者左邊 第一個比自己大或者小的元素的位置，此時我們就要想到可以用單調棧了。
- 單調棧的遞增 or 遞減順序都是按照【從棧頭 → 棧尾】
- 單調棧中存放的元素是數組元素的下标
- 每日溫度（739）
- 描述：給定一個一維數組，傳回一個數組，數組元素是每個元素到右邊第一個比自己大的元素位置距離，沒有比自己大的置0。
- 單調棧：
- 題目右邊第一個大自己的元素位置，是以單調棧要【遞增，注意從棧頭 → 棧尾】
- 初始化：
- st.push(0)【第一個元素下标】
-
// 保持棧單調遞增（從棧頭到棧尾遞增） for (int i = 1; i < temperatures.size(); i++) { // < 棧頂，直接push if (temperatures[i] < temperatures[st.top()]) st.push(i); // == 棧頂，題目要求找第一個>，不是≥，直接push else if (temperatures[i] == temperatures[st.top()]) st.push(i); else{ // 彈出<的元素，保持遞增，同時更新距離結果 while (!st.empty() && temperatures[i] > temperatures[st.top()]) { // 彈出的元素結果更新：目前周遊元素（比彈出的大）下标 - 彈出元素下标 res[st.top()] = i - st.top(); st.pop(); } st.push(i); } } - 邏輯優化
// 優化不需要初始化push(0),直接從0開始比哪裡 for (int i = 0; i < temperatures.size(); i++) { // 直接進行彈出操作，隻有不滿足遞增的情況才會進行 while (!st.empty() && temperatures[i] > temperatures[st.top()]) { // 彈出的元素結果更新：目前周遊元素（比彈出的大）下标 - 彈出元素下标 res[st.top()] = i - st.top(); st.pop(); } // st.push(i); }
- 下一個更大元素 I（496）
- 描述：給定兩個沒有重複元素一維數組，其中nums1是nums2的子集，傳回一個數組，數組元素是nums1每個元素在nums2中，右邊第一個比自己大的元素值，沒有比自己大的置-1
-
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
- 和上一題的不同之處：
- 傳回數組大小 = nums1的大小
- 在周遊nums2的時候，在更新res時，需要判斷目前周遊元素是否在num1中，再進行更新;
- 由于題目說明數組沒有重複元素，是以可以用unordered_map（haspmap）對nums1進行映射
- 單調棧：
- 題目右邊第一個大自己的元素位置，是以單調棧要【遞增，注意從棧頭 → 棧尾】
- 初始化：
- st.push(0)【第一個元素下标】
-
for (int i = 1; i < nums2.size(); i++) { // 保持遞增 if (nums2[i] < nums2[st.top()]) st.push(i); else if (nums2[i] == nums2[st.top()]) st.push(i); else{ // 彈出，保持遞增，同時更新結果 while (!st.empty() && nums2[i] > nums2[st.top()]) { // 跟上一題不一樣的地方 // 更新時，需要判斷元素是否在nums1中 if (umap.count(nums2[st.top()]) > 0){ // 擷取彈出元素在nums1中的下标 int index = umap[nums2[st.top()]]; res[index] = nums2[i]; } st.pop(); } st.push(i); } } - 邏輯優化：和上一題一樣
2022/9/9【單調棧】
- 下一個更大元素 II（503）
- 描述：給定一個循環數組，傳回一個數組，數組元素是每個元素到右邊第一個比自己大的元素位置距離，沒有比自己大的置-1。
- 和每日溫度（739）基本一緻，唯一的差別在于這是個循環數組
- 循環數組應對方法：
- 将兩個數組拼接，然後進行周遊計算，最後隻取一半長度的結果數組。【直覺，但需要額外空間】
- 直接利用取餘的計算周遊數組兩次，以及更新
-
// 使用第二種處理方式 for (int i = 0; i < nums.size()*2; i++) { while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) { result[st.top()] = nums[i % nums.size()]; st.pop(); } st.push(i % nums.size()); }
- 接雨水（42，hard）
- 有多種實作方式
- 按行計算雨水：
- 單調棧
代碼随想錄一刷個人記錄
- 單調棧
- 按列計算雨水：
- 雙指針
- 動态規劃（雙指針的優化）
代碼随想錄一刷個人記錄
- 按行計算雨水：
- 按行計算雨水：單調棧
- 單調棧内元素的順序（從棧頭 → 棧尾）：
- 要按從小到大，因為一旦周遊的位置高度 > 棧頭的高度，就說明出現了凹槽，這個時候就要計算雨水的面積；
- 單調棧内儲存的數值：
- 隻需要存入下标，下标就等同于寬度，高度可以通過height[st.top()]擷取
-
分情況讨論（三種情況）：
① 周遊的位置高度 < 棧頭的高度，直接push；
② 周遊的位置高度 == 棧頭的高度，相當于兩個高度相同的柱子挨在一起，是沒有凹槽的，隻取右邊的柱子下标：先pop()，在push；
代碼随想錄一刷個人記錄 【注意：但實際實作中，為了統一①和②，可以不進行pop()，這樣可以了解為兩個高度相同的柱子挨在一起，形成的凹槽高度 == 0，即在計算凹槽高度的時候會得到0，相當于無效更新】
③ 周遊的位置高度 > 棧頭的高度：
a. 目前周遊位置 == 右邊的柱子
b. 棧頭 == 凹槽底部（中間），記錄凹槽底部高度，彈出棧頭；
c. 如果這時棧不空，則現在的棧頭 == 左邊的柱子，計算高、寬，統計面積【這個時候不需要彈出左邊柱子，因為它可能成為下一個凹槽底部】
- 代碼實作
st.push(0); int sum = 0; for (int i = 1; i < height.size(); i++) { // 第一種情況 if (height[i] < height[st.top()]) { st.push(i); } // 第二種情況 // 如果目前周遊高度 == 棧頭高度，隻取右邊的高度下标 // 因為兩個高度相同的柱子挨在一起，是沒有凹槽的 else if (height[i] == height[st.top()]) { // 這裡加不加其實都可以， st.pop(); // 可以把兩個相同高度柱子形成的凹槽了解成0高度 st.push(i); } // 第三種情況 else{ while (!st.empty() && height[i] > height[st.top()]) { // 取凹槽中間 int mid = st.top(); st.pop(); if (!st.empty()){ // h = 左右兩邊柱子取最小高度 - 凹槽中間高度 // 左邊柱子不要彈出，可能會充當下一個凹槽 int h = min(height[i], height[st.top()]) - height[mid]; // w 要去掉兩邊柱子 int w = i - st.top() - 1; sum += h * w; } } st.push(i); } }
- 複雜度：
- 時間複雜度：O(n)
- 空間複雜度：O(n)
- 邏輯優化：
- 隻保留第③種情況的代碼，把第①種和第②種情況合并（第②種情況沒有寫pop）
- 其他要點：
- 對于多行的雨水，單調棧是按照從下往上順序計算每一行的雨水，且這一層的左邊柱子會充當上一層的凹槽底部。
- 對于第②種情況不寫pop()，在計算雨水的時候，會把右邊的柱子當作凹槽底部，左邊的柱子就是左邊的柱子（廢話），這樣在計算凹槽高度就會得到0，相當于一次無效更新。
- 單調棧内元素的順序（從棧頭 → 棧尾）：
- 有多種實作方式
2022/9/10【接雨水補充】
- 接雨水（42，hard）
-
按列計算雨水：
【如果按照列來計算的話，雨水的寬度一定是1，隻要把每一列的雨水的高度求出來就可以了。
每一列雨水的高度，取決于，該列左側最高的柱子和右側最高的柱子中最矮的那個柱子的高度。】
- 雙指針法
- 思路：每個位置（除了開頭和結尾）都向兩邊周遊，尋找左邊的最高高度和右邊的最高高度，則雨水的高度 = min(lheight, rheight) - height[i]
- 複雜度：
- 時間複雜度：O(n ^ 2)
- 空間複雜度：O(1)
- 動态規劃
- 由于雙指針每次都要向兩邊周遊，尋找最高高度，周遊過程是有重複計算的。是以可以使用動态規劃提前算出每個位置的左邊最高高度和右邊最高高度。
- 動态數組定義：
- maxLeft[i]：表示i下标左邊的最高高度
- 遞推公式：maxLeft[i] = max(maxLeft[i-1], height[i])
- maxRight[i]：表示i下标右邊的最高高度
- 遞推公式：maxRight[i] = max(maxRight[i+1], height[i])
- maxLeft[i]：表示i下标左邊的最高高度
- 初始化：
- maxLeft[0] = height[0];
- maxRight[height.size()-1] = height[height.size()-1];
- 複雜度：
- 時間複雜度：O(n)
- 空間複雜度：O(n)
- 雙指針法
-
2022/9/11【柱狀圖中最大的矩形】
- 柱狀圖中最大的矩形（84，hard）
- 【和接雨水很類似，但細節不同，同樣有三個方法】
- 整體思路：
- 找每個柱子左右兩邊第一個小于該柱子高度的柱子，以目前柱子為高，兩邊第一個小于的柱子下标差為寬，計算面積。
- 實作：
- ①單調棧：
- 單調棧内元素的順序（從棧頭 → 棧尾）：
- 根據整體思路看，要按從大到小，因為一旦周遊的位置高度 < 棧頭的高度，就說明找到了右邊第一個小于的柱子，這個時候就要計算面積；
- 單調棧内儲存的數值：
- 隻需要存入下标，下标就等同于寬度，高度可以通過height[st.top()]擷取
-
分情況讨論（三種情況，和接雨水完全一樣）：
① 周遊的位置高度 > 棧頭的高度，直接push；
② 周遊的位置高度 == 棧頭的高度，相當于兩個高度相同的柱子挨在一起，是沒有凹槽的，隻取右邊的柱子下标：先pop()，在push；
③ 周遊的位置高度 < 棧頭的高度：
a. 目前周遊位置 == 右邊第一個小于中間的柱子
b. 棧頭 == 中間位置，記錄中間位置高度，彈出棧頭；
c. 則現在的棧頭 == 左邊第一個小于中間的柱子，計算高、寬，統計面積
- 代碼實作（邏輯優化）
/* 1. 如果以第一列為高計算面積，由于其左邊沒有元素，是以在開頭插入0； 2. 同理，如果以最後一列為高計算面積，右邊沒有元素，是以在末尾插入0； */ heights.insert(heights.begin(), 0); // 數組頭插入0 heights.push_back(0); // 數組尾插入0 st.push(0); int res = 0; for (int i = 1; i < heights.size(); i++) { while (!st.empty() && heights[i] < heights[st.top()]) { // 擷取中間 int mid = st.top(); st.pop(); // 擷取左右下标，由于首尾都插入0，不會有st空的情況 int left = st.top(); int right = i; // 擷取寬度、高度 int w = right - left - 1; int h = heights[mid]; res = max(res, w*h); } st.push(i); } return res; - 複雜度：
- 時間複雜度：O(n)
- 空間複雜度：O(n)
- 需要特别注意的點：
- 代碼在原數組中額外添加了兩個0，原因看上方代碼注釋。
- 單調棧内元素的順序（從棧頭 → 棧尾）：
- ②雙指針（可以不額外添加元素0）：
- 思路：每個位置（包括開頭和結尾）都向兩邊周遊，尋找左右兩邊第一個小于的位置下标，然後求寬度
- 跟接雨水的不同：
- 周遊時要包括首尾，因為首尾也可以作為中間高度
- 複雜度：
- 時間複雜度：O(n ^ 2)
- 空間複雜度：O(1)
- ③動态規劃（好像跟動态沒啥關系。。。）
- 提前算出左右兩邊第一個小于目前位置的下标
- 和接雨水的不同：
- 數組存放的是下标，不是高度
- 動态數組定義：
- minLeftIndex[i]：表示i下标左邊第一個高度 < 目前位置的下标
- 遞推公式：
-
// 錯誤示範，這是錯的！！！ // 因為minLeftIndex[i-1]對應的高度不一定就 < heights[i] if (heights[i] < heights[i-1]) minLeftIndex[i] = i-1; else minLeftIndex[i] = minLeftIndex[i-1]; -
// 正确示範 for (int i = 1; i < heights.size(); i++) { int t = i-1; while (t >= 0 && heights[t] >= heights[i]) { // 每次跳轉到t位置，左邊第一個高度 < 目前位置的下标 t = minLeftIndex[t]; } minLeftIndex[i] = t; }
-
- 遞推公式：
- minRightIndex[i]：表示i下标右邊第一個高度 < 目前位置的下标
- 遞推公式：
// 和上面的類似 for (int j = heights.size()-2; j >= 0; j--) { int t = j + 1; while (t < heights.size() && heights[t] >= heights[j]) { t = minRightIndex[t]; } minRightIndex[j] = t; }
- 遞推公式：
- minLeftIndex[i]：表示i下标左邊第一個高度 < 目前位置的下标
- 初始化：
- minLeftIndex[0] = -1;
- minRightIndex[heights.size()-1] = heights.size();
- 複雜度：
- 時間複雜度：O(n^2)？？？
- 空間複雜度：O(n)
- ①單調棧：
額外題目：
2022/9/12【額外題目：數組】
- 有多少小于目前數字的數字（1365）
- 描述：給定一個數組，對于每個元素，統計數組中比它小的所有數字的數目，以數組形式傳回。
- 暴力法（雙層周遊）：
- 時間複雜度：O（n^2）
- 空間換時間：
- 對數組進行排序，每個元素的下标 == 比它小的數字數目
- 不能對原數組進行排序，要保留原數組的元素位置關系
- 可以使用hash表 or 數組記錄元素值和下标的映射：
- 記錄過程對于相同的數值，隻需要記錄最左邊的下标
- 方法：
- 周遊記錄時，判斷該處元素是否已經記錄過（hash表能否找到 or 數組是否已經指派）
- 使用倒序周遊記錄
- 複雜度：
- 時間複雜度：O（nlogn）
- 空間複雜度：O（n）
- 有效的山脈數組（941）
- 描述：給定一個數組，判斷是否是山脈（在數組中間存在一個位置，左邊嚴格遞增，右邊嚴格遞減）
- 采用雙指針，分别記錄左邊嚴格遞增結束的位置，右邊嚴格遞減結束的位置
- 最後判斷：
// 判斷相同的同時，還要判斷是否是在首尾位置 if (left == right && left != 0 && right != arr.size()-1) return true;
2022/9/13【額外題目：數組】
- 獨一無二的出現次數（1207）
- 描述：給定一個數組，如果每個數的出現次數都是獨一無二的，就傳回
true
false
- 思路：
- ① 使用haspmap或者數組，周遊原數組，統計每個數的出現次數；
- ② 使用haspset或者數組，周遊①中的map / 數組【不能周遊原數組，因為原數組的重複元素還在，意味着出現次數的重複】，判斷出現次數是否有重複。
- 描述：給定一個數組，如果每個數的出現次數都是獨一無二的，就傳回
- 移動零（283）
- 描述：給定一個數組，将所有 移動到數組的末尾，同時保持非零元素的相對順序。
- 思路：雙指針，使用快慢指針進行指派。
2022/9/15【額外題目：數組】
- 輪轉數組（189）
-
描述：給定一個數組，進行右旋k個元素（将k個末尾元素放在開頭）
【左旋：将開頭元素放在末尾】
- 實作：
- 和左旋操作實作類似，進行三次反轉【reverse】操作。
- 右旋：①反轉整體 ②反轉局部
- 左旋：①反轉局部 ②反轉整體
- 注意點：【 k > 數組長度 】的情況
- k > 數組長度，旋轉次數 = k % nums.size()；
- 和左旋操作實作類似，進行三次反轉【reverse】操作。
-
- 尋找數組的中心下标（724）
- 描述：給定一個數組，尋找中心下标，中心滿足左側元素和 = 右側元素和（求和不包含中心元素）
- 思路：
- 當周遊到nums[i]時，記錄左側和 = leftsum，則右側和 = total - leftsum - nums[i]，左右相等則滿足條件；
- 由上一條可知，要提前計算出數組和 total
2022/9/16【額外題目：反轉字元串相關】
- 輪轉數組（189）【2022/9/15做過】
- 右旋數組
- 左旋轉字元串（劍指Offer58-II）
- 左旋數組
- 反轉字元串（344）
- 左右雙指針交換位置
- 反轉字元串 II（541）
- for循環每次移動
2*k
- for循環每次移動
- 反轉字元串中的單詞（151）
- 描述：給定一個字元串
s
- 整體思路：
- 去除多餘空格（不去判斷多餘空格，直接全部去除，再插入）
- 反轉：
- 反轉整個字元串
- 再反轉每個單詞
-
去除多餘空格：
使用快慢指針【移除所有空格】，然後在單詞前或者後插入一個空格，
【特殊處理：要注意首尾不要有空格】，最後進行resize。
- 描述：給定一個字元串
要點注意：
- 棧stack和隊列queue的預設底層實作是雙端隊列deque
- list的底層是deque，vector的底層是普通數組
- list的插入隻需要配置設定一個節點的空間（同時修改前後指針），不需要重新拷貝所有元素；
- vector插入可能涉及擴容，需要另外配置設定擴容的空間，再重新拷貝所有元素；是以涉及數組插入優先使用list
- 一般數組的初始化長度隻能是常量（arr[100] = {0}）