Find N3入網(wǎng)：最高支持16+1TB
OPPO將于近期登場(chǎng)的Find N3折疊屏目前已經(jīng)正式入網(wǎng)，型號(hào)為PHN110。本次Find N3在外觀方面相比前兩代有很大的變化，不再是小號(hào)的橫向折疊屏，而是跟別的廠商一樣采用了較為常見(jiàn)的
要弄明白什么是棧，我們需要先舉一個(gè)生活中的例子。
假如有一個(gè)又細(xì)又長(zhǎng)的圓筒，圓筒一端封閉，另一端開(kāi)口。往圓筒里放 入乒乓球，先放入的靠近圓筒底部，后放入的靠近圓筒入口。
那么，要想取出這些乒乓球，則只能按照和放入順序相反的順序來(lái)取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球優(yōu)先取出。
棧（stack）是一種線性數(shù)據(jù)結(jié)構(gòu)，它就像一個(gè)上圖所示的放入乒乓球的 圓筒容器，棧中的元素只能先入后出 （First In Last Out，簡(jiǎn)稱FILO ）。最早進(jìn)入的元素存放的位置叫作棧底 （bottom），最后進(jìn)入的元素 存放的位置叫作棧頂 （top）。
棧這種數(shù)據(jù)結(jié)構(gòu)既可以用數(shù)組來(lái)實(shí)現(xiàn)，也可以用鏈表來(lái)實(shí)現(xiàn)。
棧的數(shù)組實(shí)現(xiàn)如下。
棧的鏈表實(shí)現(xiàn)如下。
那么，棧可以進(jìn)行哪些操作呢？棧的最基本操作是入棧和出棧，下面讓我們來(lái)看一看。
入棧操作（push）就是把新元素放入棧中，只允許從棧頂一側(cè)放入元素，新元素的位置將會(huì)成為新的棧頂。
這里我們以數(shù)組實(shí)現(xiàn)為例。
出棧操作（pop）就是把元素從棧中彈出，只有棧頂元素才允許出棧，出棧元素的前一個(gè)元素將會(huì)成為新的棧頂。
這里我們以數(shù)組實(shí)現(xiàn)為例。
入棧和出棧操作，時(shí)間復(fù)雜度分別是多少？
入棧和出棧只會(huì)影響到最后一個(gè)元素，不涉及其他元素的整體移動(dòng)，所以無(wú)論是以數(shù)組還是以鏈表實(shí)
現(xiàn)，入棧、出棧的時(shí)間復(fù)雜度都是O(1) 。
單調(diào)遞增棧 從棧底到棧頂?shù)脑仃P(guān)鍵字的大小單調(diào)遞增；
單調(diào)遞減棧 從棧底到棧頂?shù)脑仃P(guān)鍵字的大小單調(diào)遞減；
適用問(wèn)題：
要知道單調(diào)棧的適用于解決什么樣的問(wèn)題，我們首先需要知道單調(diào)棧的作用。單調(diào)棧分為單調(diào)遞增棧和單調(diào)遞減棧，通過(guò)使用單調(diào)棧我們可以訪問(wèn)到下一個(gè)比他大（小）的元素（或者說(shuō)可以）。
也就是說(shuō)在隊(duì)列或數(shù)組中，我們需要通過(guò)比較前后元素的大小關(guān)系來(lái)解決問(wèn)題時(shí)我們通常使用單調(diào)棧。
有一個(gè)地方要傳授武林秘籍，大家要在這一天之前來(lái)這里排好隊(duì)等著學(xué)習(xí)武林秘籍。來(lái)了很多武林高手，但是這個(gè)地方的人要根據(jù)人來(lái)的先后順序教，先來(lái)的學(xué)的武功就高深，來(lái)的越靠后學(xué)的就越差，但是能保證只要來(lái)就能學(xué)到。假如他們一開(kāi)始有一個(gè)初始的排隊(duì)順序和武力水平如下所示，大家可以按照這個(gè)初始順序從前往后學(xué)習(xí)。
問(wèn)題來(lái)了，武力值高的肯定愿意先學(xué)習(xí)到高深一點(diǎn)的武功啊，那我就找到前面武力值低的人說(shuō)：“你別學(xué)了，我教你一門(mén)武功，然后離開(kāi)，否則就咔嚓了你??”，武力值低的那聽(tīng)就答應(yīng)了也就只能無(wú)可奈何的打印了，從后來(lái)的那個(gè)人那里哪里學(xué)了一門(mén)武術(shù)就離開(kāi)了，這樣武功高的那個(gè)就排在了前面。下面我們來(lái)從前往后模擬一下過(guò)程：
（1）首先來(lái)的是炮灰甲，炮灰甲一看，OK，棧內(nèi)沒(méi)有人就可以先排在第一位
（2）然后掃地僧來(lái)了，掃地僧教給了炮灰甲一招易筋經(jīng)，然后掃地僧讓炮灰甲離開(kāi)自己排在第一位。
（3）然后楊過(guò)過(guò)來(lái)，看到前面是掃地僧，自己打不過(guò)只能老老實(shí)實(shí)站到隊(duì)里。
（4）后面一直來(lái)人（如3）------ 直到張三 對(duì)里面站的是 掃地僧 楊過(guò) 慕容復(fù) 張三 。
（5）然后張無(wú)忌來(lái)了，他首先看到前面是張三，張無(wú)忌教給張三一招武當(dāng)梯云縱，然后讓張三離開(kāi)了，張無(wú)忌再往前看到了慕容復(fù)教他一招太極拳，然后繼續(xù)直到遇到掃地僧，OK，自己打不過(guò)，老老實(shí)實(shí)的占到了后面 —現(xiàn)在隊(duì)里有掃地僧，張無(wú)忌 ----楊過(guò)，慕容復(fù)，張三的師傅為張無(wú)忌
（6）柯鎮(zhèn)惡來(lái)了，打不過(guò)，站到后面就好了。
（7）然后喬峰來(lái)了把柯鎮(zhèn)惡和張無(wú)忌打發(fā)走， —現(xiàn)在隊(duì)里有掃地僧，喬峰。
（8）然后李四來(lái)了，打不過(guò)喬峰，只能站到了最后。
（9）第二天掃地僧，喬峰，李四成功學(xué)到了武林秘籍
現(xiàn)在看他們分別學(xué)到武功對(duì)應(yīng)如下圖：
這樣我們就處理完了所有過(guò)程。因此單調(diào)棧的時(shí)間復(fù)雜度為O(n),在比較時(shí)對(duì)出棧的元素有一個(gè)處理（例如掃地僧讓炮灰甲走的時(shí)候教給他自己的武功），另外最后留在站內(nèi)的元素有一個(gè)統(tǒng)一的處理（掃地僧，喬峰，李四成功學(xué)到了武林秘籍）。
偽代碼如下所示：
對(duì)于第i個(gè)到來(lái)的人：
思路：有了單調(diào)棧的基本認(rèn)識(shí)，我們可以遍歷每根柱子，以當(dāng)前柱子 i 的高度作為矩形的高，那么矩形的寬度邊界即為向左找到第一個(gè)高度小于當(dāng)前柱體 i 的柱體，向右找到第一個(gè)高度小于當(dāng)前柱體 i 的柱體。對(duì)于每個(gè)柱子我們都如上計(jì)算一遍以當(dāng)前柱子作為高的矩形面積，最終比較出最大的矩形面積即可。
單調(diào)棧實(shí)現(xiàn)：尋找兩邊距離arr[i]最近且arr[i]小的索引，保持棧頂?shù)綏５讍握{(diào)遞減，棧中存放索引值。
注意：頭0如果不添加，尋找左邊元素需要判斷棧是否為空；尾0如果不添加，需要重新寫(xiě)一個(gè)循環(huán)彈出棧內(nèi)元素。
class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; int [] left = new int[n]; int [] right = new int[n]; Stack<Integer> stack = new Stack<>(); for(int i = 0; i < n; i++){ while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){ stack.pop(); } left[i] = (stack.isEmpty() ? -1: stack.peek()); stack.push(i); } stack.clear(); for(int i = n-1; i >= 0; i--){ while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){ stack.pop(); } right[i] = (stack.isEmpty() ? n : stack.peek()); stack.push(i); } int res = 0; for(int i = 0; i < n; i++){ res = Math.max(res, (right[i] - left[i] - 1) * heights[i]); } return res; }}該題目有多種解法，本次只介紹單調(diào)棧的方式，對(duì)其它算法感興趣的朋友可以自己去嘗試一下~~
思路：理解題目注意題目的性質(zhì)，當(dāng)后面的柱子高度比前面的低時(shí)，是無(wú)法接雨水的，當(dāng)找到一根比前面高的柱子，就可以計(jì)算接到的雨水。所以使用單調(diào)遞減棧：
class Solution { public int trap(int[] height) { int ans = 0; Stack<Integer> stack = new Stack<Integer>(); int n = height.length; for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) { break; } int left = stack.peek(); int currWidth = i - left - 1; int currHeight = Math.min(height[left], height[i]) - height[top]; ans += currWidth * currHeight; } stack.push(i); } return ans; }}本文鏈接：http://www.www897cc.com/showinfo-26-5102-0.html數(shù)組結(jié)構(gòu)~什么是單調(diào)棧
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： 如何優(yōu)雅地處理RabbitMQ中的消息丟失
下一篇： 聊聊如何理解流量分發(fā)
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)