大廠(chǎng)算法和數(shù)據(jù)結(jié)構(gòu)解析中

鏈表（LinkedList）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線(xiàn)性表，但是并不會(huì)按線(xiàn)性的順序數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針（Pointer由于不必須按順序，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線(xiàn)性——順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(n)和O(1)。示例輸入輸入1->2->3->4->5-輸出5->4->3->2->1-進(jìn)階next指向之前的節(jié)點(diǎn)就可以了。1→2→3→nullnull←1←2←3next指針改為指向publicpublicclassReverseLinkedListpublicListNodereverseList(ListNodehead){ListNodecurr=head;ListNodeprev=while(curr!=ListNodetempNext=curr.next;curr.next=prev;prev=curr;curr=tempNext;}return}}時(shí)間復(fù)雜度：O(n)nO(n)假設(shè)鏈表為（ n1→n2→…→nk?1→nk→nk+1→…→nm→ nknk+1nm n1→n2→…→nk?1→nk→nk+1←…←nk+1nk，所以，應(yīng)該有nk+1.next=nkpublicpublicListNodereverseList(ListNodehead)if(head==null||head.next==null){returnhead;}ListNoderestHead=ListNodereversedRest restHead.next=head;head.next=null;returnreversedRest;}時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(n)，假設(shè)n是鏈表的長(zhǎng)度，那么時(shí)間復(fù)雜度為O(n)。輸入：輸入：1->2->41->3-list1list2。只要它們都不為空，就取出當(dāng)前它們各自的頭節(jié)點(diǎn)就（sentinelpublicpublicclassMergeTwoSortedListspublicListNodemergeTwoLists(ListNodel1,ListNodel2)ListNoderesultPrev=newListNode(-ListNodeListNodeprev=while(l1!=null&&l2!=nullif(l1.val<=l2.val){prev.next=l1;prev=l1;l1=l1.next;}elseprev.next=l2;prev=l2;l2=}}prev.next=(l1==null)?l2:return}}時(shí)間復(fù)雜度：O(n+m)n和ml1和l2while循環(huán)的次數(shù)不會(huì)超過(guò)兩個(gè)鏈表的長(zhǎng)度之和。所有其他操作的時(shí)間復(fù)雜度都是常數(shù)級(jí)別的，因此總的時(shí)間復(fù)雜度為O(n+m)publicpublicListNodemergeTwoLists(ListNodel1,ListNodel2)if(l1==nullreturnelseif(l2==nullreturnif(l1.val<=l2.vall1.next=mergeTwoLists(l1.next,return}elsel2.next=mergeTwoLists(l1,return}}時(shí)間復(fù)雜度：O(n+m)nnm分別為兩個(gè)鏈表的長(zhǎng)度。因?yàn)槊看握{(diào)用遞歸都l1l2的頭節(jié)點(diǎn)（直到至少有一個(gè)鏈表為空mergeTwoList至多只會(huì)遞歸調(diào)用每個(gè)節(jié)點(diǎn)一次。因此，時(shí)間復(fù)雜度取決于合并后的鏈表長(zhǎng)度，即O(n+m)?？臻g復(fù)雜度：O(nm)nmmergeTwoLists函數(shù)時(shí)需要消耗?？臻g，?？臻g的大小取決于遞歸調(diào)用的深度。結(jié)束遞歸調(diào)用時(shí)mergeTwoLists函數(shù)最多調(diào)用n+m次，因此空間復(fù)雜度為O(n+m)。n給定一個(gè)鏈表給定一個(gè)鏈表1->2->3->4->5,n1->2->3-n保證是有效的。javaJVMGC最簡(jiǎn)單的想法是，我們首先從頭節(jié)點(diǎn)開(kāi)始對(duì)鏈表進(jìn)行一次遍歷，得到鏈表的長(zhǎng)度L。然后，我們?cè)購(gòu)念^節(jié)點(diǎn)開(kāi)始對(duì)鏈表進(jìn)行一次遍歷，當(dāng)遍歷到第L-N+1個(gè)節(jié)點(diǎn)時(shí)，它就NpublicpublicclassRemoveNthNodeFromEndpublicListNoderemoveNthFromEnd(ListNodehead,intn)intl=ListNodesentinel=newListNode(-1);sentinel.next=head;ListNodecurr=for(inti=0;i<l-n;i++){curr=curr.next;}curr.next=return}publicstaticintgetLength(ListNodeintlength=while(head!=null){length++;head=}return}}時(shí)間復(fù)雜度：O(L)L是鏈表的長(zhǎng)度。只用了兩次遍歷，是線(xiàn)性時(shí)間復(fù)雜度。n個(gè)節(jié)點(diǎn)就是需要?jiǎng)h除的節(jié)點(diǎn)，并且目前棧頂?shù)墓?jié)點(diǎn)就是待刪除節(jié)publicpublicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodesentinel=newListNode(-1);sentinel.next=Stack<ListNode>stack=newStack<>();ListNodecurr=sentinel;while(curr!=null){curr=curr.next;}for(inti=0;i<n;i++){}stack.peek().next=return}<=空間復(fù)雜度：O(L)Lfirstsecondfirstsecond超前N個(gè)節(jié)點(diǎn)。Nfirst遍歷到鏈表的末尾（null）時(shí)，second就恰L-N+1，也就是倒數(shù)第N個(gè)節(jié)點(diǎn)了。publicpublicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodesentinel=newListNode(-1);sentinel.next=ListNodefirst=sentinel,second=for(inti=0;i<n+1;i++){first=first.next;}while(first!=null){first=first.next;second=second.next;}second.next=return}時(shí)間復(fù)雜度：O(L)L是鏈表的長(zhǎng)度。這次真正實(shí)現(xiàn)了一次遍歷。據(jù)結(jié)構(gòu)也就是說(shuō)它通過(guò)把關(guān)鍵字值映射到表中一個(gè)位置來(lái)記錄以加快查找的速度。pair的key快速value。哈希表在不考慮的情況下，插入、刪除和操作時(shí)間復(fù)雜度均為O(1)設(shè)計(jì)一個(gè)哈希表，有兩個(gè)問(wèn)題需要去解決如何設(shè)計(jì)哈希方法（哈希函數(shù)哈希方法（hashmethod，也叫哈希函數(shù)）會(huì)將鍵值映射到某塊空間映射到同一個(gè)空間，這種情況稱(chēng)為“哈希碰撞”（HashCollision，也叫“哈希?，F(xiàn)（Java中就是用鏈表來(lái)實(shí)現(xiàn)的示例1:輸入輸入輸出輸入輸入輸出publicintpublicintsingleNumber(int[]nums){List<Integer>singleList=newArrayList<>();for(Integernum:nums){if(singleList.contains(num))}return}時(shí)間復(fù)雜度：O(n^2)numsO(n)判斷是否存在這個(gè)數(shù)字，再花費(fèi)O(n)的時(shí)間，所以總循環(huán)時(shí)間為O(n^2)?？臻g復(fù)雜度：O(n)nnumsHashMap中，這樣查詢(xún)的時(shí)候不就不用再遍歷一次了。publicpublicintsingleNumber(int[]nums)Map<Integer,Integer>singleMap=newfor(Integernum:nums)if(singleMap.get(num)!=null)singleMap.put(num,}return}時(shí)間復(fù)雜度：O(n)。forO(n)HashMapget操作時(shí)間復(fù)雜O(1)?？臻g復(fù)雜度：O(n)。HashMapnumssetset2，publicintpublicintsingleNumber3(int[]nums){Set<Integer>set=newHashSet<>();intarraySum=0;IntegersetSum=for(intnum:nums){arraySum+=num;}}for(Integernum:set)setSum+=num;returnsetSum*2-})空間復(fù)雜度：O(n)。HashSetnums0XORXOR0XOR滿(mǎn)換律和結(jié)合XORpublicpublicintsingleNumber(int[]nums)intresult=for(intnum:nums)result^=num;return}時(shí)間復(fù)雜度：O(n)n是數(shù)組長(zhǎng)度。只需要對(duì)數(shù)組遍歷一次。給定一個(gè)未排序的整數(shù)數(shù)組nums，找出數(shù)字連續(xù)的最長(zhǎng)序列（不要求序列元素在原O(n)示例輸入：輸入：nums[1,2,3,4]4。示例2：輸入：輸入：nums0<=nums.length<=-109<=nums[i]<=（publicpublicclassLongestConsecutiveSequencepublicintlongestConsecutive(int[]nums)intmaxLength=for(inti=0;i<nums.length;intcurrNum=intcurrLength=while(contains(nums,currNum+1)){currLength++;currNum}if(currLength>maxLength)maxLength=currLength;}return}publicstaticbooleancontains(int[]nums,intfor(intnum:numsif(num==xreturn}return}}}O(N^3)。publicpublicintlongestConsecutive(int[]nums)intmaxLength=HashSet<Integer>hashSet=newfor(intnum:nums)for(inti=0;i<nums.length;intcurrNum=intcurrLength=while(hashSet.contains(currNum+1)){currLength++;currNum}if(currLength>maxLength)maxLength=currLength;}}return}時(shí)間復(fù)雜度：O(N^2)HashSet需要。后面由于簡(jiǎn)化了內(nèi)層循環(huán)中判斷后繼的過(guò)程只耗費(fèi)O(1)時(shí)間所以最終是內(nèi)外兩重循環(huán)情況下時(shí)間復(fù)雜度為O(N^2)。O(N)的內(nèi)存空間。xx,x+1,x+2,?,x+y的連續(xù)序列。并且，我們可以確定，這種情況得到的結(jié)果（連續(xù)序列的長(zhǎng)度x為publicpublicintlongestConsecutive(int[]nums)intmaxLength=HashSet<Integer>hashSet=newfor(intnum:nums)for(inti=0;i<nums.length;i++)intcurrNum=intcurrLength=ifif(!hashSet.contains(currNum-1))while(hashSet.contains(currNum+1)){}if(currLength>maxLength)maxLength=}}return}時(shí)間復(fù)雜度：O(N)O(n)的時(shí)間復(fù)雜度，只有當(dāng)一個(gè)數(shù)是連續(xù)序列的第LRU緩存機(jī)制運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)LRU(最近最少使用)緩存機(jī)制。實(shí)現(xiàn)LRUCache類(lèi)：LRUCache(intcapacity)以正整數(shù)作為容量capacityLRUintget(intkey)key-1O(1)["LRUCache","put","put","get","put","get","put","get","get",[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[null,null,null,1,null,-1,null,-1,3,LRUCacheLRUCachelRUCachenewLRUCache(2);lRUCache.put(1,1);//緩存是{1=1}lRUCache.put(22);{1=1, lRUCache.put(3,3);//該操作會(huì)使得關(guān)鍵字2作廢，緩存是{1=1,3=3} //返回-1(未找到)lRUCache.put(4,4);//該操作會(huì)使得關(guān)鍵字1作廢，緩存是{4=4,3=3} //返回-1(未找到) 1<=capacity<=0<=key<=0<=value<=3*104get和LRU（Leastrecentlyused，最近最少使用）果數(shù)據(jù)最近被過(guò)，那么將來(lái)被的幾率也更高。可以用一個(gè)HashMap來(lái)作為緩存的數(shù)據(jù)結(jié)構(gòu)。這樣，我們的和插入，就都可以以HashMap要有一個(gè)容量限制；而且當(dāng)達(dá)LRU的策略刪除最近最少使用的那個(gè)數(shù)據(jù)。這就要求須把數(shù)據(jù)，按照一定的線(xiàn)性結(jié)構(gòu)排列起來(lái)，的數(shù)據(jù)放在后面，新數(shù)據(jù)的插入可“頂?shù)糇钋懊娴牟怀５臄?shù)據(jù)這種數(shù)據(jù)結(jié)構(gòu)其實(shí)可以用鏈表來(lái)實(shí)現(xiàn)。所以，我們最終可以使用一個(gè)哈希表+LRU哈希表”——LinkedHashMap。它本身繼承了HashMap，而它的節(jié)點(diǎn)Entry除了繼承自HashMap.Nodebeforeafter兩個(gè)指針，從而實(shí)現(xiàn)了雙向鏈表。publicpublicclassLRUCacheextendsLinkedHashMap<Integer,privateintpublicLRUCache(intcapacity){super(capacity,0.75f,true);this.capacity=capacity;}publicintget(intkey)return}publicvoidput(intkey,intvalue)super.put(key,}protectedbooleanremoveEldestEntry(Map.Entry<Integer,Integer>eldest){returnreturnsize()>}}publicpublicclassLRUCacheclassNodeintkey;intvalue;Nodeprev;NodepublicNode()publicNode(intkey,intvalue)this.key=this.value=}}privateintcapacity;privateintsize;privateNodehead,tail;publicLRUCache(intcapacity)this.capacity=this.size=head=newtail=newhead.next=tail.prev=}publicintget(intkey)Nodenode=if(node==null)return-}return}publicvoidput(intkey,intvalue)Nodenode=if(node!=null)node.value=}elseNodenewNode=newNode(key,hashMap.put(key,sizeif(size>capacity)Nodetail=size--}}}privatevoidmoveToTail(Nodenode)}privatevoidremoveNode(Nodenode.prev.next=node.next.prev=}privatevoidaddToTail(Nodenode)node.next node.prev=tail.prev.next tail.prev }privateNoderemoveHead()NoderealHead=return}}時(shí)間復(fù)雜度：O(1)HashMapputget空間復(fù)雜度：O(capacity)，因?yàn)楣１砗碗p向鏈表最多capacity+1個(gè)元素（超出緩capacity+1。（LIFO）在具體應(yīng)用中通常用鏈表或者數(shù)組來(lái)實(shí)現(xiàn)。隊(duì)列只允許在后端（稱(chēng)為rear）進(jìn)行插入操作，端（稱(chēng)為front）進(jìn)行刪除操作。(Deque:doubleended8首先出隊(duì)：有元素，時(shí)間復(fù)雜度O（n，并不是最理想的方式。因此，一般是用大頂堆（MaxHeap，有時(shí)也叫最大堆）來(lái)實(shí)現(xiàn)最大優(yōu)先隊(duì)列，每一次5119O(logn)。O(logn)。push(x)--xpop()--top()--empty()--注意你只能使用隊(duì)列的基本操作--pushtoback,peek/popfromfront,size,isempty這些操作是合法的。listdeque（雙端隊(duì)列）來(lái)模,只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。你可以假設(shè)所有操作都是有效的（例如,poptop操式；區(qū)別在于，元素進(jìn)出的方式不同。可以增加一個(gè)隊(duì)列來(lái)做輔助。我們記原始負(fù)責(zé)數(shù)據(jù)的隊(duì)列為queue1，新增的輔助queue2。queue2中本沒(méi)有數(shù)據(jù)，所以當(dāng)前元素一定在隊(duì)首。queue1：ab接下來(lái)，就讓queue1queue2中來(lái)。這樣，queue2queue2：xab最后queue2的內(nèi)容給queue1做然后清空queue2在代碼上，queue1queue2指向的內(nèi)容即可。queue1：xabqueue1publicclasspublicclassMyStack{Queue<Integer>queue1;Queue<Integer>queue2;publicMyStack(){queue1=newqueue2=new}publicvoidpush(intx)whilequeue2.offer(queue1.poll()}Queue<Integer>temp=queue1;queue1=queue2;queue2=}publicintpop()return}publicinttop()return}publicbooleanempty()return}}O(n)O(1)pushqueue1nn+1queue2，總計(jì)2n+1次操作。每次出隊(duì)和入隊(duì)操作的時(shí)間復(fù)雜度都是O(1)，因此入棧操作的時(shí)間復(fù)雜度是O(n)。popqueue1的隊(duì)首元素出隊(duì)，時(shí)間復(fù)雜度是O(1)。topqueue1O(1)。isEmptyqueue1O(1)空間復(fù)雜度：O(n)，其中n是棧內(nèi)的元素。需要使用兩個(gè)隊(duì)列棧內(nèi)的元素xqueue1，x移動(dòng)到隊(duì)首了。publicpublicclassMyStack2Queue<Integer>publicMyStack2()queue=new}publicvoidpush(intx)intl=for(inti=0;i<l;queue.offer(queue.poll()}}publicintpop()return}publicinttop()return}publicbooleanempty()return}}O(n)O(1)pushqueue1nn+1queue2，總計(jì)2n+1次操作。每次出隊(duì)和入隊(duì)操作的時(shí)間復(fù)雜度都是O(1)，因此入棧操作的時(shí)間復(fù)雜度是O(n)。popqueue1的隊(duì)首元素出隊(duì)，時(shí)間復(fù)雜度是O(1)。topqueue1O(1)。isEmptyqueue1O(1)空間復(fù)雜度：O(n)，其中n是棧內(nèi)的元素。需要使用兩個(gè)隊(duì)列棧內(nèi)的元素emptyMyQueuevoidpush(intx)xintpop()intpeek()booleanempty()true你只能使用標(biāo)準(zhǔn)的棧操作——pushtotop,peek/popfromtop,isempty你所使用的語(yǔ)言也許不支持棧。你可以使用list或者deque（雙端隊(duì)列）來(lái)模擬你能否實(shí)現(xiàn)每個(gè)操作均攤時(shí)間復(fù)雜度為O(1)的隊(duì)列？換句話(huà)說(shuō)，執(zhí)行n個(gè)操作的總時(shí)間復(fù)雜度為O(n)，即使其中一個(gè)操作可能花費(fèi)較長(zhǎng)時(shí)間。["MyQueue","push","push","peek","pop",[[],[1],[2],[],[],[null,null,null,1,1,MyQueuemyQueue=newMyQueue();myQueue.push(1);MyQueuemyQueue=newMyQueue();myQueue.push(1);//queueis:myQueue.push(2);//queueis:[1,2](leftmostisfrontofthequeue)myQueue.peek();//return1myQueue.pop();//return1,queueismyQueue.empty();//return1<=x<=100push、pop、peek（poppeek操作FIFO的特性，我們需要將入棧的元素次序進(jìn)行反轉(zhuǎn)，這樣在出隊(duì)時(shí)就可以按照入隊(duì)順序依元素是最先入隊(duì)的元素，而入隊(duì)的元素要壓入棧底。我們可以用一個(gè)棧來(lái)元素的最終順序（隊(duì)列順序，記作stack1；用另一個(gè)進(jìn)行輔stack2。stack2pushstack2stack1，進(jìn)行反轉(zhuǎn)。publicclasspublicclassMyQueue{Stack<Integer>stack1;Stack<Integer>stack2;publicMyQueue(){stack1=newstack2=new}publicvoidpush(intx)while}while}}publicintpop()return}publicintpeek()return}publicbooleanempty()return}}除新元外，所有元素都會(huì)被壓入兩次，彈出兩次。新元素被壓入兩次，彈出一次（stack1清空之后把新元素直接壓入，就只壓入一次了）4n+3n是隊(duì)列的大小。由于入棧操作和彈出操作的時(shí)O(1)O(n)需要額外的內(nèi)存來(lái)隊(duì)列中的元素stack1stack1中所有元stack2stack2的棧頂元素。stack1stack2中的棧頂元素就可以了。publicclassMyQueue2Stack<Integer>Stack<Integer>publicMyQueue2()stack1=newstack2=new}publicvoidpush(intx)}publicintpop()ifwhile}}return}publicintpeek()ifwhile}}return}publicbooleanempty()returnstack1.isEmpty()&&}}}入隊(duì)空間復(fù)雜度：O(n)。需要額外的內(nèi)存（stack1和stack2共同）來(lái)隊(duì)列元素出隊(duì)時(shí)間復(fù)雜度：攤還復(fù)雜度O(1)，情況下的時(shí)間復(fù)雜度在情況下，stack2為空，算法需要執(zhí)行while循環(huán)進(jìn)行反轉(zhuǎn)。具體過(guò)程是從nnstack2n代表隊(duì)列的大小。這個(gè)過(guò)程產(chǎn)生了2n步操作，時(shí)間復(fù)雜度為O(n)。但當(dāng)stack2非空時(shí)，只需要直接彈棧，算法就只有O(1)的時(shí)間復(fù)雜度。均攤下來(lái)，O(1)。攤還分析（Amortizedysis，均攤法，用來(lái)評(píng)價(jià)某個(gè)數(shù)據(jù)結(jié)構(gòu)的一系列操作的平均，攤還分析的在于情況下的操作一旦發(fā)生了一次，那么在未來(lái)很長(zhǎng)一段時(shí)間都，是平均操作。在攤還分析中，不涉及概率，并且保證在情況下每一個(gè)操作的平均性能'('，')'，'{'，'}'，'['，示例輸入輸入輸出輸入輸入輸出輸入輸入輸出輸入輸入輸出輸入輸入 輸出: 由于給定字符串中只包含'('，')'，'{'，'}'，'['，']'，所以我們不需要額外考慮字符false。publicpublicclassValidParenthesespublicbooleanisValid(Strings){Deque<Character>stack=newLinkedList<>();for(inti=0;i<s.length();i++){charc=if(c=='('}elseif(c=='['}elseif(c=='{'}elseifif(stack.isEmpty())returnfalse;charright=stack.pop();if(c!=right)return}}return}}時(shí)間復(fù)雜度：O(n)ns的長(zhǎng)度。只需要遍歷一次字符串。n個(gè)非負(fù)整數(shù)，用來(lái)表示柱狀圖中各個(gè)柱子的高度。每個(gè)柱子彼此相鄰，且寬度為1。1[2,1,5,6,2,3]10示例輸入輸入輸出（即矩形面積計(jì)算中的長(zhǎng)和寬publicpublicclassLargestRectangleInHistogrampublicintlargestRectangleArea1(int[]heights)intlargestArea=forfor(intleft=0;left<heights.length;left++intcurrHeight=for(intright=left;right<heights.length;right++){currHeight=(heights[right]<currHeight)?heights[right]:intcurrArea=(right-left+1)*currHeight;largestArea=(currArea>largestArea)?currArea:}}return}}publicpublicintlargestRectangleArea(int[]heights)intlargestArea=for(inti=0;i<heights.length;i++intintheight=intleft=i,right=while(left>=0if(heights[left]<height)break;left--;}while(right<heights.lengthif(heights[right]<height)break;right++;}intwidth=right-left-intcurrArea=height*largestArea=currArea>largestArea?currArea:}return}O(N^2)。publicpublicintlargestRectangleArea(int[]heights)intn=heights.length;int[]lefts=newint[n];int[]rights=newint[n];intlargestArea=0;for(inti=0;i<n;i++){intheight=heights[i];intleft=i-1;while(left>=0if(heights[left]<height)break;left=lefts[left];}lefts[i]=}for(inti=n-1;i>=0;i--intheight=intright=i+while(right<nif(heights[right]<height)break;right=rights[right];}rights[i]=}for(inti=0;i<n;i++intintcurrArea=(rights[i]-lefts[i]-1)*heights[i];largestArea=currArea>largestArea?currArea:largestArea;}return}時(shí)間復(fù)雜度：O(N)。我們發(fā)現(xiàn)，while循環(huán)內(nèi)的判斷比對(duì)總體數(shù)量其實(shí)是有限的。每次O(N)。空間復(fù)雜度：O(N)n[6,7,5,2,4,5,9,3]66-1。隨后我們將6入棧。我們枚舉7，由于6<7，因此不會(huì)移除棧頂元素，所以7左側(cè)的柱子是6置為0。隨后7入棧。棧：[6(0),7(1)]57≥576≥5，再移除棧頂元素6。此時(shí)棧為空，所以5左側(cè)的柱子是「哨兵，位置為?1。隨后5入棧。接下來(lái)的枚舉過(guò)程也大同小異。我們枚舉2，移除棧頂元素5，得到2左側(cè)的?1。將2入棧。453，45。將它們?nèi)霔?。棧：[2(3),4(4),5(5),9(6)]39，54323。將3入棧。棧：[2(3[?1,0,?1,?1,3,4,5,3]用相同的方法，我們從右向左進(jìn)行遍歷，也可以得到它們右側(cè)的柱子編號(hào)分別為[2,2,3,8,7,7,7,8]，這里位置8看作右側(cè)的“哨兵publicpublicintlargestRectangleArea(int[]heights)intn=heights.length;int[]lefts=newint[n];int[]rights=newint[n];intlargestArea=0;Stack<Integer>stack=newfor(inti=0;i<n;i++while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){}lefts[i]=stack.isEmpty()?-1:stack.peek();}for(inti=n-1;i>=0;i--while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){}rights[i]=stack.isEmpty()?n:stack.peek();}for(inti=0;i<n;i++intcurrArea=(rights[i]-lefts[i]-1)*heights[i];largestArea=currArea>largestArea?currArea:largestArea;}return}的總時(shí)間復(fù)雜度為O(N)。publicpublicintlargestRectangleArea(int[]heights)intn=heights.length;int[]lefts=newint[n];int[]rights=newfor(inti=0;i<n;i++)rights[i]=intlargestArea=Stack<Integer>stack=newfor(inti=0;i<n;i++while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){rights[stack.peek()]=i;}lefts[i]=stack.isEmpty()?-1:stack.peek();}for(inti=0;i<n;i++intcurrArea=(rights[i]-lefts[i]-1)*heights[i];largestArea=currArea>largestArea?currArea:largestArea;}return}空間復(fù)雜度：O(N)O(N)。將數(shù)值以哈希（hash）或分桶（bucket）的形式直接映射到空間來(lái)實(shí)現(xiàn)的。選擇排序（Selection冒泡排序（Bubble插入排序（InsertionO(1)。排序（S。1959年由S發(fā)明，是第一個(gè)突破O(n2)的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素排序又叫縮小增量。1。的增量序列如Hibbard經(jīng)過(guò)復(fù)雜證明可使得時(shí)間復(fù)雜度為O(n^3/2)。歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法andConquer）2-路歸并。O(nlognlists“基準(zhǔn)”（pivot，中心，支點(diǎn)；publicpublicclassQuickSortpublicstaticvoidqSort(int[]nums,intstart,intendif(start>=endintmid=partition(nums,start,qSort(nums,start,mid-1qSortqSort(nums,mid+1,end}privatestaticintpartition(int[]nums,intstart,intendintpivot=intleft=intright=while(left<rightwhile(left<right&&nums[right]>=pivot)right--;nums[left]=while(left<right&&nums[left]<=pivot)left++;nums[right]=}nums[left]=return}}堆排序（Heap（MaxHeapO(nlogn)。k不是很大并且序列比較集中時(shí)，計(jì)數(shù)排序是一個(gè)很有效的排序算法。桶排序(Bucketsort)的工作原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)基數(shù)排序（Radix到最。O(n+k)kn>>k，因此額外n個(gè)左右。k個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第k示例輸入輸入3,2,1,5,6,4]k輸出輸入輸入3,2,3,1,2,4,5,5,6]k輸出說(shuō)明k總是有效的，且1kK大的元素，首先能想到的，當(dāng)然就是直接排序。只要數(shù)組是有序的，K個(gè)元素就可以了。publicpublicclass ementpublicintfindKthLargest(int[]nums,intk){returnnums[nums.length-}}我們知道，javaArrays.sort()O(nlogn)。對(duì)子數(shù)組進(jìn)行劃分，如果劃分得到的位置q正好就是我們需要的下標(biāo)，就直接返回a[q]；否則，如果q比目標(biāo)下標(biāo)小，就遞歸右子區(qū)間，否則遞歸左子區(qū)間。這樣就可以把原來(lái)遞隨機(jī)化來(lái)加速這個(gè)過(guò)程，它的時(shí)間代價(jià)的期望是O(n)。publicpublicintfindKthLargest(int[]nums,intk)returnquickSelect(nums,0,nums.length-1,nums.length-k}publicintquickSelect(int[]nums,intstart,intend,intindexintq=randomPatition(nums,start,endif(q==return}elsereturnq>index?quickSelect(nums,start,q-1,index):quickSelect(nums,q+1,end,index);}}publicintrandomPatition(int[]nums,intstart,intend){Randomrandom=newRandom();intrandIndex=start+random.nextInt(end-start+1);swap(nums,start,randIndex);returnpartition(nums,start,}publicintpartition(int[]nums,intstart,intendintpivot=intleft=intright=while(left<rightwhile(left<right&&nums[right]>=pivot)right--;nums[left]=while(left<right&&nums[left]<=pivot)left++;nums[right]=}nums[left]=return}publicvoidswap(int[]nums,inti,intjinttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}空間復(fù)雜度：O(logn)O(logn)。k?1次刪除操作后堆頂元素就是我們要找的答案。publicpublicintfindKthLargest(int[]nums,intk)intn=intheapSize=buildMaxHeap(nums,heapSizefor(inti=n-1;i>n-k;i--){swap(nums,0,i);heapSize--maxHeapify(nums,0,heapSize}return}publicvoidbuildMaxHeap(int[]nums,intheapSizefor(inti=heapSize/2-1;i>=0;i--){maxHeapify(nums,i,heapSize);}}publicvoidmaxHeapify(int[]nums,inttop,intheapSizeintleft=top*2+1;intright=top*2+2;intlargest=top;ifif(right<heapSize&&nums[right]>nums[largest]){largest=right;}if(left<heapSize&&nums[left]>nums[largest]){largest=left;}if(largest!=topswap(nums,top,largest);maxHeapify(nums,largest,heapSize);}}時(shí)間復(fù)雜度：O(nlogn)O(n)，k-1O(klogn)，因?yàn)閗<n，故漸進(jìn)時(shí)間復(fù)雜為O(n+klogn)=O(nlogn)。n個(gè)元素的數(shù)組，原地對(duì)它們進(jìn)行排序，使得01和2示例1：輸入：輸入：nums示例輸入：輸入：nums示例輸入：輸入：nums示例輸入：輸入：numsn==1<=n<=nums[i]0、1EdsgerWDijkstra首先提出。3種顏色的條紋拼接而成，如下圖所示：JavapublicpublicvoidsortColors(int[]nums){}如果用選擇排序的思路，我們可以通過(guò)遍歷數(shù)組，找到當(dāng)前最?。ɑ蜃畲蟮臄?shù)012publicpublicvoidsortColors(int[]nums)intcurr=for(inti=0;i<nums.length;ifif(nums[i]==0swap(nums,curr++,i}}for(inti=0;i<nums.length;if(nums[i]==1swap(nums,curr++,i}}}publicvoidswap(int[]nums,inti,intjinttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}時(shí)間復(fù)雜度：O(n)，nnums的長(zhǎng)度。需要遍歷兩次數(shù)組。0，1，2publicpublicclassSortColorspublicvoidsortColors(int[]nums)intcount0=0,count1=0,count2=for(intnum:numsif(num==0)count0++;elseif(num==1)count1++;count2}for(inti=0;i<nums.length;i++if(i<count0)nums[i]=0;elseif(i<count0+count1)nums[i]=1;nums[i]=}}}時(shí)間復(fù)雜度：O(n)，nnums的長(zhǎng)度。需要遍歷兩次數(shù)組。02移到數(shù)組尾，1保持不變就可publicpublicvoidsortColors(int[]nums)intleft=0,right=nums.length-inti=while(left<right&&i<=rightwhile(i<=right&&nums[i]==2)swap(nums,i,right--);if(nums[i]==0swap(nums,i,left++);}}時(shí)間復(fù)雜度：O(n)，nnums的長(zhǎng)度。雙指針?lè)ㄖ惶摫闅v一次數(shù)組。給出一個(gè)區(qū)間的集合，請(qǐng)合并所有的區(qū)間示例輸入輸入intervals輸出解釋區(qū)間[1,3]輸入輸入intervals輸出解釋區(qū)間[1,4][4,5]intervals[i][0]<=a2a1<=b2。也就是說(shuō)，如果某個(gè)子區(qū)間的左邊界在另一子區(qū)間內(nèi)，那么它們可以合很明顯，這樣的算法，時(shí)間復(fù)雜度不會(huì)低于O(n^2)。有沒(méi)有更好的方式呢publicpublicclassMergeIntervalspublicint[][]merge(int[][]intervals){List<int[]>result=newArrayList<int[]>();Arrays.sort(intervals,newComparator<int[]>()publicintcompare(int[]o1,int[]o2)returno1[0]-}for(int[]interval:intervalsintleft=interval[0],right=intlength=if(length==0||left>result.get(length-1)[1]){}elseintmergedLeft=result.get(length-intmergedRight=Math.max(result.get(length-right}}}returnresult.toArray(new}}時(shí)間復(fù)雜度：O(nlogn)，其中n為區(qū)間的數(shù)量。除去排序的開(kāi)銷(xiāo)，我們只需要一次線(xiàn)性?huà)呙?，所以主要的時(shí)間開(kāi)銷(xiāo)是排序的O(nlogn)?？臻g復(fù)雜度：O(logn)，其中n為區(qū)間的數(shù)量。O(logn)即為快速排序所需要的空間復(fù)樹(shù)是一種非線(xiàn)性n（n>=0）（rootTm-1，每個(gè)集合都是一棵樹(shù)，稱(chēng)為根結(jié)點(diǎn)的（subtree。節(jié)點(diǎn)的度：節(jié)點(diǎn)擁有的個(gè)（leaf：樹(shù)的高度：樹(shù)點(diǎn)的最大層數(shù)，也叫做樹(shù)的深二叉樹(shù)（Binary的兩個(gè)，一般叫做節(jié)點(diǎn)的左和右。0i2^i個(gè)結(jié)點(diǎn)k2^(k+1)1個(gè)結(jié)點(diǎn)(k>=-1)(空樹(shù)的高度為-(0)數(shù)為m,2n,則m+（Recursion一個(gè)簡(jiǎn)單示例就是計(jì)算階乘：01；nn-npublicstaticintfactorial(intif(n==0)returnreturnfactorial(n-1)*}publicstaticintfact(intacc,intif(n==0)returnreturnfact(acc*n,n-1}return語(yǔ)句之前，這種形式的iipublicstaticvoidprintTreePreOrder(TreeNoderoot){if(root==null)return;System.out.print(root.val+"\t");printTreePreOrder(root.left);printTreePreOrder(root.right}publicstaticvoidprintTreeInOrder(TreeNoderootif(root==null)return;printTreeInOrder(root.left);System.out.print(root.val+"\t");printTreeInOrder(root.right);}publicstaticvoidprintTreePostOrder(TreeNoderootif(root==null)return;printTreePostOrder(root.left);printTreePostOrder(root.right);System.out.print(root.val+"\t");}publicstaticvoidprintTreeLevelOrder(TreeNodepublicstaticvoidprintTreeLevelOrder(TreeNoderoot){Queue<TreeNode>queue=newLinkedList<>();while(!queue.isEmpty()TreeNodecurNode=System.System.out.print(curNode.val+"\t");if(curNode.left!=null)if(curNode.right!=null)}}二叉搜索樹(shù)（BinarySearch任意節(jié)點(diǎn)左如果不為空，則左點(diǎn)的值均小于根節(jié)點(diǎn)的任意節(jié)點(diǎn)右如果不為空，則右點(diǎn)的值均大于根節(jié)點(diǎn)的任意節(jié)點(diǎn)的左右，也分別是二叉搜索nO(logN)。n個(gè)節(jié)點(diǎn)的線(xiàn)性鏈表。如下圖平衡二叉搜索樹(shù)：簡(jiǎn)稱(chēng)平衡二叉樹(shù)。由前的數(shù)學(xué)家Adelse-Velskil和Landis在年高度平衡的二叉樹(shù)，根據(jù)科學(xué)家的英文名也稱(chēng)為AVL樹(shù)。1棵樹(shù)的左右的高度之差超過(guò)1，如左的樹(shù)高為2，右的樹(shù)高為0，樹(shù)高差2就打破了這個(gè)平衡。AVL樹(shù)是帶有平衡條件的二叉搜索樹(shù)，它是嚴(yán)格的平衡二叉樹(shù)，平衡條件必須滿(mǎn)足(所有節(jié)點(diǎn)的左右高度差不超過(guò)1)。不管我們是執(zhí)行插入還是刪除操作，只要不滿(mǎn)足上面AVLWindows進(jìn)程地址空間樹(shù)（Red-Black。樹(shù)是一種特殊的二叉查找樹(shù)樹(shù)的每個(gè)節(jié)點(diǎn)上都有位表示節(jié)點(diǎn)的顏色，可。每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)旋轉(zhuǎn)等操作，讓新的樹(shù)符合所有規(guī)則。AVL樹(shù)多用于搜索,插入,刪除操作多的情況下。樹(shù)應(yīng)用比較廣泛C++STL中，mapset都是用紅黑樹(shù)實(shí)現(xiàn)的。Java中的TreeSet，TreeMap也都是用樹(shù)實(shí)現(xiàn)的。著名的linux進(jìn)程調(diào)度 yFairScheduler，用樹(shù)管理進(jìn)程控制塊epoll在內(nèi)核中的實(shí)現(xiàn)，用樹(shù)管理nginx中，用樹(shù)管理timerB樹(shù)（B-B樹(shù)(B-Tree)是一種自平衡的樹(shù)，它是一種多路搜索樹(shù)（并不是二叉的，能夠保證數(shù)據(jù)有序。同時(shí)，BO(logn)，為大塊數(shù)據(jù)的讀寫(xiě)操作做了優(yōu)化，同時(shí)它也可以用來(lái)描述外部。M根結(jié)點(diǎn)的兒子數(shù)為[2,除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2M/2-1（取上整）M-12非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)–非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1],K[2],K[M-1]K[i]指向關(guān)鍵字大于K[M-1]的，其它P[i]指向關(guān)鍵字屬于(K[i-1],K[i])的M3BB+B+B-B+樹(shù)只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹(shù)可以在非葉非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引，葉子結(jié)點(diǎn)相當(dāng)于是（關(guān)鍵B+層級(jí)更低，IOB+樹(shù)的主要原因。4 // / 3 4 72/ / 6 publicpublicTreeNodeinvertTree(TreeNoderoot){if(root==null)returnnull;TreeNodetemp=root.left;root.left=root.right;root.right=temp;invertTree(root.left);invertTree(root.rightreturnreturn}的高度。在平均情況下，二叉樹(shù)的高度與節(jié)點(diǎn)個(gè)數(shù)為對(duì)數(shù)關(guān)系，即O(logN)。而在情況O(N)。publicpublicTreeNodeinvertTree(TreeNoderoot){if(root==null)returnnull;TreeNodeleft=invertTree(root.left);TreeNoderight=invertTree(root.right);root.left=right;root.right=return}一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn)的左右兩個(gè)的高度差的絕對(duì)值不超過(guò)1示例輸入：root輸入：root示例輸入：root輸入：root示例輸入：輸入：root（類(lèi)似先序遍歷）或者自底向上（類(lèi)似后序遍歷容易想到的一個(gè)方法是，從根節(jié)點(diǎn)開(kāi)始，自頂向下遞歸地判斷左右是否平衡publicpublicclassBalancedBinaryTreepublicbooleanisBalanced(TreeNoderoot)if(root==null)returnreturnMath.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&