棧篇

題目71：給你一個(gè)字符串?path?，將其轉(zhuǎn)化為更加簡(jiǎn)潔的linux規(guī)范路徑。

思路：因?yàn)樯婕暗椒祷厣弦患?jí)目錄簿训，就要用棧。

題目155：設(shè)計(jì)一個(gè)支持?push?米间，pop?强品，top?操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧屈糊。

MinStack()?初始化堆棧對(duì)象的榛。 push(int val)?將元素val推入堆棧。pop()?刪除堆棧頂部的元素逻锐。 top()?獲取堆棧頂部的元素夫晌。 getMin()?獲取堆棧中的最小元素。

思路：既然要按順序保存元素昧诱，那就不能用單調(diào)棧慷丽。那最小元素就用另一個(gè)輔助棧來記錄最小值。

push 入棧的時(shí)候鳄哭，與輔助棧頂?shù)脑乇容^大小要糊，如果小的話，也入輔助棧。pop出棧的時(shí)候锄俄，記得檢查一下是否是最小元素局劲，如果是，輔助棧也要pop奶赠。如果不是鱼填，就不用管。（因?yàn)闂ｍ斣卦谳o助棧那邊也是在最頂?shù)囊愀辏绻皇菞ｍ斣仄煌瑁f明沒有入輔助棧）

題目224：給你一個(gè)只包含 數(shù)字加減括號(hào) 和 空格 的字符串表達(dá)式?s，如：? "(1+(4+5+2)-3)+(6+8)"苇经，請(qǐng)實(shí)現(xiàn)一個(gè)基本計(jì)算器來返回它的值赘理。

思路：1. 首先，要把字符串轉(zhuǎn)變成 符號(hào) 括號(hào) 和 數(shù)字 組成的列表扇单。特別是多位數(shù)字要小心處理商模。

2.? 因?yàn)槔ㄌ?hào)內(nèi)的要先計(jì)算。因此碰到左括號(hào)蜘澜，就先把前面的值和符號(hào)（num, sign）入棧施流，然后初始化num, sign，逐個(gè)加減括號(hào)內(nèi)元素鄙信，得到一個(gè)值瞪醋。碰到右括號(hào)說明括號(hào)內(nèi)計(jì)算完畢，彈出之前的（num, sign）作為 prev_num, prev_sign 装诡，然后 num = prev_num + prev_sign * num

題目394：給定一個(gè)經(jīng)過編碼的字符串银受，返回它解碼后的字符串。如s = "3[a2[c]]"?返回"accaccacc"

思路：多層括號(hào)慎王，務(wù)必手動(dòng)驗(yàn)證一下棧的邏輯蚓土。

由于數(shù)字是乘上其身后括號(hào)里面的字符串。因此可以把已有的字符串和數(shù)字做成元組 (pre_char, num) 放入stack. 直到括號(hào)里面的字符串解碼完畢赖淤，碰到右括號(hào)蜀漆，就彈出(pre_char, num) 用?pre_char + num * (括號(hào)內(nèi)解碼完畢的字符串)

題目735：給定一個(gè)小行星數(shù)組?asteroids，正負(fù)表示移動(dòng)方向咱旱。找出碰撞后剩下的所有小行星确丢。

碰撞規(guī)則：兩個(gè)小行星相互碰撞，較小的小行星會(huì)爆炸吐限。如果兩顆小行星大小相同鲜侥，則兩顆小行星都會(huì)爆炸。

思路：由于有正負(fù)兩個(gè)方向诸典，stack記錄正向移動(dòng)的小行星描函。同時(shí)有可能有一個(gè)負(fù)向移動(dòng)的小行星擊穿所有正向行星，因此還要一個(gè)away來記錄負(fù)向行星。

單調(diào)棧篇

題目901：設(shè)計(jì)一個(gè)算法返回股票當(dāng)日價(jià)格的?跨度?舀寓〉ㄊ跨度?被定義為股票價(jià)格小于或等于今天價(jià)格的最大連續(xù)日數(shù)。例如互墓，如果未來 7 天股票的價(jià)格是?[100,80,60,70,60,75,85]必尼，那么股票跨度將是?[1,1,1,2,1,4,6]?。

實(shí)現(xiàn)?StockSpanner?類：StockSpanner()?初始化類對(duì)象篡撵。int next(int price)?給出今天的股價(jià)?price?判莉，返回該股票當(dāng)日價(jià)格的?跨度?。

思路寫在代碼里了育谬，模擬一遍棧就懂券盅。

隊(duì)列篇

題目933：寫一個(gè)RecentCounter類來計(jì)算特定時(shí)間范圍內(nèi)最近的請(qǐng)求。

RecentCounter()?初始化計(jì)數(shù)器斑司，請(qǐng)求數(shù)為 0 渗饮。int ping(int t)?在時(shí)間?t?添加一個(gè)新請(qǐng)求但汞，并返回在?[t-3000, t]?內(nèi)發(fā)生的請(qǐng)求數(shù)宿刮。

思路：超過3000的請(qǐng)求就要舍棄。先進(jìn)先出私蕾，用隊(duì)列僵缺。每次請(qǐng)求的時(shí)候添加 t ，同時(shí)把超過3000的popleft()踩叭，然后返回隊(duì)列的長(zhǎng)度磕潮。

題目649：Dota2 參議院由D R 兩派的參議員組成。他們按senate的順序逐輪投票容贝。每一位參議員都可以讓另一位參議員在這一輪和隨后的幾輪中喪失?所有的權(quán)利?自脯。宣布勝利：如果參議員發(fā)現(xiàn)有權(quán)利投票的參議員都是?同一個(gè)陣營(yíng)的?，則游戲勝利斤富。

思路：按順序行使權(quán)力膏潮，那最優(yōu)策略就是讓對(duì)方最靠前的那個(gè)參議院失去權(quán)力。因此使用兩個(gè)隊(duì)列满力，分別記錄兩黨參議院的編號(hào)焕参。然后逐對(duì)比較，編號(hào)靠后者失去權(quán)力退出游戲油额。而編號(hào)靠前者加入隊(duì)伍末端叠纷，此時(shí)編號(hào)要加n.

優(yōu)先隊(duì)列/堆 篇

題目215: 給定整數(shù)數(shù)組?nums?和整數(shù)?k，請(qǐng)返回?cái)?shù)組中第?k?個(gè)最大的元素潦嘶。時(shí)間復(fù)雜度為?O(n)?

思路：堆排序的時(shí)間復(fù)雜度是O(nlog(n))涩嚣，所以用堆來實(shí)現(xiàn)O(n)算法有些難度。這里我們假設(shè)k為遠(yuǎn)小于n的數(shù)。那時(shí)間復(fù)雜度還能約等于O(n)

題目502：給你?n?個(gè)項(xiàng)目航厚。對(duì)于每個(gè)項(xiàng)目?i?校摩，它都有一個(gè)純利潤(rùn)?profits[i]?，和啟動(dòng)該項(xiàng)目需要的最小資本?capital[i]?阶淘。最初衙吩，你的資本為?w?。當(dāng)你完成一個(gè)項(xiàng)目時(shí)溪窒，你將獲得純利潤(rùn)坤塞，且利潤(rùn)將被添加到你的總資本中〕喊觯總而言之摹芙，從給定項(xiàng)目中選擇?最多?k?個(gè)不同項(xiàng)目的列表，以?最大化最終資本?宛瞄，并輸出最終可獲得的最多資本浮禾。

思路：本題陷阱很多！首先份汗，把項(xiàng)目按照投資額排序盈电。第二步，由于投資項(xiàng)目個(gè)數(shù)有限杯活，因此每次投資都要拿到最大的利潤(rùn)匆帚。必須用堆！把項(xiàng)目按照利潤(rùn)入最大堆旁钧。然后彈出利潤(rùn)最大的項(xiàng)目吸重，更新本金。循環(huán)k次歪今。

題目373：給定兩個(gè) 非遞減順序排列?的整數(shù)數(shù)組?nums1?和?nums2?,?以及一個(gè)整數(shù)?k?嚎幸。定義一對(duì)值(u,v)，其中第一個(gè)元素來自nums1寄猩，第二個(gè)元素來自?nums2?嫉晶。請(qǐng)找到和最小的?k個(gè)數(shù)對(duì)(u1,v1),?(u2,v2)?...(uk,vk)。

思路：i, j 是nums1 nums2 中的索引, i, j 都有可能取到很大焦影。但全部?jī)蓛上嗉尤ヅ判蛱速M(fèi)時(shí)間復(fù)雜度车遂。(i+1, j+1) 能夠取到的先決條件是（i+1, j）和 （i, j+1）都被取到了。那就可以用類似動(dòng)態(tài)規(guī)劃的思路斯辰，i 為行舶担，j為列。

初始化就把第一行 nums1[0] + nums2[j] 都加入最小堆彬呻。每次從最小堆中取出一對(duì)數(shù)組衣陶，然后加入下一行的元素nums1[i+1] + nums2[j]柄瑰。列取到 j ，意味著下一行的元素nums1[i+1] + nums2[k] k<j 都已經(jīng)塞進(jìn)去了剪况，不會(huì)遺漏教沾。

題目295：求取數(shù)據(jù)流的中位數(shù)。實(shí)現(xiàn) MedianFinder 類: MedianFinder() 初始化?MedianFinder對(duì)象译断。void addNum(int num)?將數(shù)據(jù)流中的整數(shù)?num?添加到數(shù)據(jù)結(jié)構(gòu)中授翻。double findMedian()?返回到目前為止所有元素的中位數(shù)。與實(shí)際答案相差10-5以內(nèi)的答案將被接受孙咪。

思路：用兩個(gè)堆來實(shí)現(xiàn)堪唐。用最小堆存放數(shù)據(jù)流中的較大一半元素；用最大堆存放數(shù)據(jù)流中的較小 一半元素翎蹈。兩個(gè)堆形成上下對(duì)稱的兩個(gè)倒三角淮菠。三角塔尖就是中位數(shù)。

添加元素的時(shí)候荤堪，必須在兩個(gè)堆中都遍歷一遍合陵，才能保證上三角的元素都大于下三角。

題目2336：實(shí)現(xiàn)?SmallestInfiniteSet?類：SmallestInfiniteSet()?初始化：無限集包含所有正整數(shù)澄阳。int popSmallest()?移除并返回該無限集中的最小整數(shù)拥知。void addBack(int num)?如果正整數(shù)?num?不?存在于無限集中，則將一個(gè)?num?添加?到該無限集最后寇荧。

肯定不可能真的實(shí)現(xiàn)無限集合举庶，那就看功能执隧，滿足功能的要求即可揩抡。

思路：取正整數(shù)的最小值嘛，那肯定從1開始取镀琉。如果沒有中途添加元素峦嗤，那就每次按照一個(gè)順序 self.smallest 1 2 3 ...這樣返回即可。如果有添加過元素屋摔，那就看取出來的按原定順序取出來的元素self.smallest還是中途添加的元素烁设，如果是中途添加的元素，self.smallest不用+1. 同時(shí)在添加過的元素集合self.added_set中丟去這個(gè)中途添加的元素钓试。

中途添加元素的功能装黑，如果比當(dāng)前的最小整數(shù)self.smallest大，就根本不用添加弓熏。如果小的話恋谭，就看有沒有在添加過的元素集合self.added_set中，不在挽鞠，就加入最小堆疚颊。

思路：使用排序的集合狈孔。由于pop()功能做多用1000次，那就給一個(gè)包含[1, 1001]的排列集合就好材义。每次取最小均抽，就把第一個(gè)元素丟出來。添加元素的話其掂，集合隨意添加油挥，還帶排序。

題目2542：兩個(gè)長(zhǎng)度為n的整數(shù)數(shù)組nums1和nums2款熬。選擇長(zhǎng)度為 k 的 子序列喘漏，使得：(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 最大。

思路：由于在nums2中华烟，我們?nèi)〉氖亲钚≈掉媛酢Ｄ蔷涂梢园凑課ums2排序，先取到第k個(gè)值盔夜，此時(shí)的nums2[k]就是最小值负饲，然后乘上nums1的累加和，算出得分喂链。然后繼續(xù)向前遍歷返十，pop掉nums1值最小的那一對(duì)，加入新的nums2椭微。如果新的得分更大洞坑，就更新。

題目2462：給定整數(shù)數(shù)組costs和兩個(gè)整數(shù)k?和candidates蝇率。costs[i]是雇傭第?i位工人的成本迟杂。總共進(jìn)行k輪雇傭本慕，且每一輪恰好雇傭一位工人排拷。在每一輪雇傭中，從最前面?candidates和最后面?candidates人中選出成本最小的一位工人锅尘，如果有多位代價(jià)相同且最小的工人监氢，選擇下標(biāo)更小的一位工人。返回雇傭k位工人的總代價(jià)藤违。

思路：“如果有多位代價(jià)相同且最小的工人浪腐，選擇下標(biāo)更小的一位工人” 那這就簡(jiǎn)單了。每一輪將left, right范圍內(nèi)的工人和下標(biāo)丟進(jìn)一個(gè)最小堆顿乒，每次取出一個(gè)议街。然后根據(jù)下表確定范圍是在left 還是在right 變化