常數(shù)時(shí)間求棧的最大值
問題描述：
一個(gè)棧stack暂雹，具有push和pop操作彬犯，其時(shí)間復(fù)雜度皆為O(1)婿着。
設(shè)計(jì)算法max操作，求棧中的最大值近她，該操作的時(shí)間復(fù)雜度也要求為O(1)叉瘩。可以修改棧的存儲方式粘捎，push薇缅，pop的操作，但是要保證O(1)的時(shí)間復(fù)雜度攒磨，空間時(shí)間復(fù)雜度無要求捅暴。
算法描述：
一個(gè)存儲所有最大值的棧Sm。
- 當(dāng)push入棧的元素大于當(dāng)前最大元素咧纠，將該元素壓入最大值棧Sm蓬痒；
- Sm棧頂始終保存棧中當(dāng)前的最大元素；
- 當(dāng)前最大元素被pop出棧時(shí)漆羔，將Sm棧頂?shù)膶?yīng)最大元素也彈出棧梧奢。
max操作即為獲得Sm棧頂最大元素。
假設(shè)元素以5,4,1,2,3,10,9,8,6,7,15順序入棧演痒，則兩個(gè)棧中存儲的元素如下圖所示：
常數(shù)時(shí)間空間求棧的最大值
問題描述：
一個(gè)整數(shù)棧stack亲轨，具有push和pop操作，其時(shí)間空間復(fù)雜度皆為O(1)鸟顺。
設(shè)計(jì)算法max操作惦蚊，求棧中的最大值，該操作的時(shí)間空間復(fù)雜度也要求為O(1)讯嫂”姆妫可以修改棧的存儲方式，push欧芽，pop的操作莉掂，但是要保證O(1)的時(shí)間空間復(fù)雜度。
算法描述：
變量Max保存當(dāng)前最大元素值千扔，初始值為最小整數(shù)m憎妙。
當(dāng)push入棧時(shí)，將（當(dāng)前元素-Max）存入棧中曲楚，
若當(dāng)前元素小于Max厘唾，棧中元素為負(fù)數(shù)；
若當(dāng)前元素大于等于Max龙誊，棧中元素為非負(fù)數(shù)抚垃，將Max替換為當(dāng)前元素。當(dāng)pop出棧時(shí)，
若棧中元素為負(fù)數(shù)讯柔，則將（棧中元素+Max）彈出棧抡蛙；
若棧中元素為非負(fù)數(shù)，則將Max彈出棧魂迄，并將Max替換為（Max-棧中元素）粗截。Max即為當(dāng)前棧中最大元素值。
主要思路是將最大值以某種方式在原有棧中標(biāo)記出來捣炬，從而減少空間使用熊昌。可以用正負(fù)數(shù)來區(qū)分普通元素和最大值元素：
普通元素使用負(fù)數(shù)存儲（元素-Max）湿酸；
最大值元素使用非負(fù)數(shù)存儲（New Max - Old Max）婿屹；
這樣便可在棧中區(qū)分普通元素和最大值元素，并可通過Max恢復(fù)Old Max推溃。
假設(shè)元素以5,4,1,2,3,10,9,8,6,7,15順序入棧昂利，則兩個(gè)棧中存儲的元素如下圖所示：
-
元素5,4,1,2,3入棧后的情況
-
元素10,9,8,6,7入棧后的情況
-
元素15入棧后的情況
-
元素15出棧時(shí)的情況
-
元素15出棧后的情況（恢復(fù)原有狀態(tài)）
