LeetCode 155題解 | 最小棧

最小棧

  • 一、題目鏈接
  • 二、題目
  • 三、算法原理
    • 思路1:用一個變量存儲最小元素
    • 思路2:雙棧普通棧和最小棧
  • 四、編寫代碼
  • 五、時間復雜度

一、題目鏈接

最小棧

二、題目

在這里插入圖片描述

三、算法原理

棧用數組、鏈表實現都行,最主要的就是在能在常數時間內檢索到最小元素的棧,說明getMin是O(1)的接口。

思路1:用一個變量存儲最小元素

用一個變量存儲最小元素,push一個值就比較一下并且要判斷是否要更新最小元素。但是若更新后再pop一下就會出問題,此時棧中最小元素也會發生改變,那么怎么更新呢?更新成什么數呢?遍歷一遍棧嗎,這樣就是O(n)的接口了,與O(1)不符。

在這里插入圖片描述

思路2:雙棧普通棧和最小棧

采用雙棧的方式來實現:普通棧(正常存取數據)和最小棧。

最小棧:若向普通棧中push的元素大于當前最小棧中的棧頂元素,就不用往最小棧中push;若向普通棧中push的元素小于等于當前最小棧中的棧頂元素或者最小棧為空,就向最小棧中push;getMin獲取最小棧中的棧頂元素即可。

在這里插入圖片描述

若再push一個與最小元素相等的元素,那么最小棧中是否也要push呢?—— 要。若沒有push,普通棧pop元素-1,此時pop了最小元素,要更新最小值最小棧也pop了,此時最小值理應還是-1而不是1。所以,push的元素比最小棧棧頂元素小或相等,minst都要push這個元素。

在這里插入圖片描述

當前棧中最小元素是-1,若pop元素7后,最小元素還是-1,此時最小棧不用動。若再pop,此時刪除的元素與最小棧中的棧頂元素相等,那么這時最小棧要pop,這時getMin就是1:

在這里插入圖片描述

不需要寫構造、析構、拷貝構造、賦值。類的兩個成員變量是自定義類型的,不寫構造,編譯器自動生成的默認構造會自動調用兩個成員變量的默認構造,拷貝構造、析構、賦值同理。

private:stack<int> _st;stack<int> _minst;

構造函數,像這樣啥也不寫或直接為空都是可以的:

在這里插入圖片描述

因為顯示寫構造了,編譯器就不會生成默認構造了。顯示寫構造,不管有沒有寫初始化列表,一個類都有初始化列表的。沒有顯示寫初始化列表且沒有給缺省值,對于自定義類型的成員會調用它的默認構造。

封裝:
封裝的簡單形態:數據和方法放到類里面,想被看到的封裝成公有,不想被看到的封裝成私有。
另一層封裝的體現:無需關心比如說像這道題的棧的底層是怎么實現的,就只管怎么用即可,知道了功能直接調用對應的功能。

四、編寫代碼

class MinStack {
public:MinStack(){}void push(int val) {_st.push(val);if (_minst.empty() || val <= _minst.top()) _minst.push(val);}void pop() {if (_st.top() == _minst.top()) _minst.pop();_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;stack<int> _minst;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

五、時間復雜度

所有接口的時間復雜度都是O(1)。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/903459.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/903459.shtml
英文地址,請注明出處:http://en.pswp.cn/news/903459.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

es+kibana---集群部署

其實一般es要跑3個節點的&#xff0c;這樣才能做高可用&#xff0c;處理并發大&#xff0c;但是我這里只是一個pod mkdir -p /stroe/data/es es搭建&#xff1a; #【拉取鏡像】 #docker pull elasticsearch:6.8.7 #docker pull busybox:1.28 【導入鏡像】 docker load -i es.…

WPF常用技巧匯總 - Part 2

WPF常用技巧匯總-CSDN博客 主要用于記錄工作中發現的一些問題和常見的解決方法。 目錄 WPF常用技巧匯總-CSDN博客 1. DataGrid Tooltip - Multiple 2. DataGrid Tooltip - Cell值和ToolTip值一樣 3. DataGrid Tooltip - Cell值和ToolTip值不一樣 4. DataGrid - Ctrl A /…

uniapp打包apk如何實現版本更新

我們做的比較簡單&#xff0c;在后端設置版本號&#xff0c;并在uniapp的config.js中定義版本號&#xff0c;每次跟后端的進行對比&#xff0c;不一致的話就更新。 一、下載apk 主要代碼&#xff08;下載安裝包&#xff0c;并進行安裝&#xff0c;一般得手動同意安裝&#xf…

局部和整體的關系

Prompt&#xff1a;為什么要研究局部和整體的關系呢&#xff1f;是因為很多情況下&#xff0c;局部就能表達出整體&#xff1f; 這是一個非常本質的問題&#xff0c;其實你已經接近數學和物理中“幾何本質”的核心了。我們研究局部和整體的關系&#xff0c;是因為&#xff1a;…

企業辦公協同平臺安全一體化生態入住技術架構與接口標準分析報告

全球組織數字化與智能化背景下 企業辦公協同平臺安全一體化生態入住技術架構與接口標準分析報告 一、背景與市場需求 市場規模與增量 根據Statista數據&#xff0c;全球協同辦公平臺市場規模預計從2023年的$480億增長至2027年的$900億&#xff0c;年復合增長率&#xff08;CAG…

【2025最新面試八股常問知識點】HTTP1.0,HTTP1.1,HTTP2.0,HTTP3.0,HTTP的進化之路。

HTTP 超文本傳輸協議&#xff08;英文&#xff1a;HyperText Transfer Protocol&#xff0c;縮寫&#xff1a;HTTP&#xff09;是一種用于分布式、協作式和超媒體信息系統的應用層協議。設計HTTP最初的目的是為了提供一種發布和接收HTML頁面的方法。通過HTTP或者HTTPS協議請求的…

【算法練習】歸并排序和歸并分治

文章目錄 1.歸并排序1.1 遞歸版本1.2 非遞歸版本 2.歸并分治2.1 計算數組的小和2.2 計算翻轉對 1.歸并排序 歸并排序的核心步驟是&#xff1a; 拆分&#xff1a;將無序數組不斷對半拆分成小塊&#xff0c;直到每個小塊只剩一個元素&#xff08;自然有序&#xff09;。 合并&a…

域對齊是什么

域對齊&#xff08;Domain Alignment&#xff09;是在機器學習和計算機視覺等領域中常用的技術 定義 域對齊旨在將不同域&#xff08;Domain&#xff09;的數據映射到一個共同的特征空間中&#xff0c;使得來自不同域的數據在該空間中具有相似的分布。這里的“域”可以指代不…

【linux】git安裝、升級

git安裝、升級 一、快捷安裝版本2.18.0二、自定義版本安裝&#xff08;安裝、升級&#xff09;1、移除舊文件2、安裝所需依賴3、選擇指定版本4、解壓文件、編譯5、增加環境變量&#xff0c;驗證是否版本 三、升級 一、快捷安裝版本2.18.0 yum install git git --version二、自…

編程日志4.24

棧的鏈表基礎表示結構 #include<iostream> #include<stdexcept> using namespace std; //模板聲明&#xff0c;表明Stack類是一個通用的模板&#xff0c;可以用于存儲任何類型的元素T template<typename T> //棧的聲明 //Stack類的聲明&#xff0c;表示一…

《冰雪傳奇點卡版》:探索冰雪世界的傳奇旅程!

《冰雪傳奇點卡版》以“純凈打金”為核心&#xff0c;摒棄復雜付費坑&#xff0c;回歸經典傳奇玩法。以下從核心玩法、資源獲取、職業搭配、交易變現四維度展開&#xff0c;助你高效開啟冰雪傳奇之旅。 一、核玩法解析&#xff1a;如何高效獲取資源&#xff1f; 1. 職業定位與…

DeepClaude開源程序可以實現代碼生成、創作詩句以及內容創作等功能

一、軟件介紹 文末提供程序和源碼下載 DeepClaude開源程序是增強的 AI&#xff0c;可以實現代碼生成&#xff1a;DeepSeek r1 Claude 3.7 十四行詩 - 無與倫比的性能&#xff01;內容創作&#xff1a;DeepSeek r1 Gemini 2.5 Pro - 卓越的質量&#xff01;OpenAI 兼容。流媒…

Java常用注解通俗解釋

注解就像是給Java代碼貼的"便利貼"&#xff0c;它們不會改變代碼本身的邏輯&#xff0c;但能給編譯器、開發工具或運行時環境提供額外信息。下面我用最通俗的方式解釋Java中最常用的注解&#xff1a; 一、基礎篇&#xff1a;人人必知的注解 1. Override - "我…

vscode chrome調試怎么在所有瀏覽器都好使

chrome調試時只能在打開的瀏覽器里進行調試&#xff0c;其它打開的chrome瀏覽器就不能調試了&#xff0c;怎么解決。 右鍵點擊 Chrome 的快捷方式圖標&#xff0c;選擇屬性 在目標一欄&#xff0c;最后加上--remote-debugging-port9222 注意要用空格隔開 lanch.json 文件配置 …

Unity PBR基礎知識

PBR原理 基于物理的渲染&#xff08;Physically Based Rendering&#xff0c;PBR&#xff09;是指使用基于物理原理和微平面理論建模的著色/光照模型&#xff0c;以及使用從現實中測量的表面參數來準確表示真實世界材質的渲染理念。 PBR基礎理念 微平面理論&#xff08;Micr…

COM組件使用方法

普通COM組件&#xff08;如DLL&#xff09;僅暴露方法/屬性接口&#xff0c;而ActiveX控件&#xff08;如OCX&#xff09;需要可視化交互&#xff08;如按鈕、表格&#xff09;&#xff0c;需通過 ??AxInterop?? 包裝器實現宿主環境集成。 項目中引入ActiveX控件流程如下。…

在 Spring Boot 項目中如何使用索引來優化 SQL 查詢?

在 Spring Boot 項目中使用索引來優化 SQL 查詢是提升數據庫性能最常用的方法之一。下面是詳細的步驟和實踐指南&#xff1a; 核心目標&#xff1a;讓數據庫能夠通過掃描索引&#xff08;小范圍、有序的數據結構&#xff09;快速定位到所需數據行&#xff0c;而不是掃描整個表…

Vue3生產環境與Vue Devtools

在 Vue 3 的生產環境中&#xff0c;默認情況下 Vue Devtools 是無法正常使用 的&#xff0c;但開發者可以通過配置強制啟用。以下是關鍵信息總結&#xff1a; &#x1f4cc; 核心結論 默認不可用 Vue 3 生產構建會移除 Devtools 支持以優化性能和安全性。 可強制啟用 通過構建…

ARP滲透學習1

ARP協議工作原理 1. 什么是ARP ARP定義: 地址解析協議&#xff08;Address Resolution Protocol&#xff09;&#xff0c;是根據IP地址獲取物理地址的一個TCP/IP協議。 2. 工作原理 ARP表: 每臺計算機都需要一個ARP表&#xff0c;用來保存IP地址和MAC地址的映射關系。查詢過…

甲骨文云2025深度解析:AI驅動的云原生生態與全球化突圍

一、戰略轉型&#xff1a;從數據庫巨頭到AI云服務先鋒 1. 技術重心向AI與云深度遷移 甲骨文在2025年加速向AI原生云架構轉型&#xff0c;其核心戰略圍繞生成式AI與量子計算展開。通過推出Oracle 23ai自治數據庫&#xff0c;深度集成AI向量搜索功能&#xff0c;并重構云基礎設…