Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

s思路： 1. 關(guān)鍵就是最小值的計(jì)算。每次進(jìn)來(lái)一個(gè)數(shù)，計(jì)算出最小值，然后把這個(gè)最小值當(dāng)個(gè)小尾巴和這個(gè)數(shù)放一起就可以了。比如，存成pair。也就是，相當(dāng)于做了distributed的操作，讓每個(gè)數(shù)進(jìn)來(lái)的時(shí)候，就告訴這個(gè)數(shù)，現(xiàn)在誰(shuí)是最小值，等有人問(wèn)現(xiàn)在最小值是多少，站在stack頂上的哥們就掏出自己知道的最小值回答他！ 2.調(diào)試的時(shí)候，容易忽略一點(diǎn)：往stack push數(shù)據(jù)時(shí)，容易想到計(jì)算當(dāng)前最小值，但往外pop數(shù)據(jù)時(shí)，卻忽略了也要重新update最小值。即使這也想到了，卻容易忽略一個(gè)極端情況：當(dāng)stack被pop空了后，當(dāng)前最小值需要回到初始化的值INT_MAX。 3. 通過(guò)一番琢磨自己的思路，發(fā)現(xiàn)思路的問(wèn)題：1. 不注重對(duì)稱性，本來(lái)更新最小值是在操作的全過(guò)程都需要的，包括push和pop，這是最大的事實(shí)，而頭腦里面的思維和這個(gè)事實(shí)還沒(méi)有明顯的對(duì)接，只是明顯知道需要在push時(shí)計(jì)算，沒(méi)有意識(shí)在pop的時(shí)候也需要計(jì)算，而push和pop是對(duì)稱的操作。以后對(duì)這種對(duì)稱的操作，都應(yīng)該同時(shí)平等的考慮，沒(méi)有誰(shuí)重要或不重要，我想這應(yīng)該是潛意識(shí)里給push進(jìn)來(lái)這個(gè)操作賦予了更高優(yōu)先級(jí)和更重要位置，從而pop這個(gè)操作就給選擇性遺忘。因此，需要打破這種人為的貼標(biāo)簽的態(tài)度，認(rèn)為某個(gè)操作重要，作為一個(gè)完整的系統(tǒng)，任何一部分都同等重要，或都不重要！ 4. 還有一點(diǎn)是：對(duì)極限的考慮。極限情況，就是當(dāng)stack空的時(shí)候，是否stack里面所有的狀態(tài)都恢復(fù)到初始狀態(tài)。這就需要有極限的思維，站在極端的情況下看問(wèn)題，看到的世界就不同。但首先需要有意識(shí)的站在極端的世界里去，就自然可以看到解決的方法！立場(chǎng)決定了視野！