Example One:
給定一個數(shù)組，它的第?i 個元素是一支給定股票第 i 天的價格慧瘤。
如果你最多只允許完成一筆交易（即買入和賣出一支股票）宜雀，設(shè)計(jì)一個算法來計(jì)算你所能獲取的最大利潤。
注意你不能在買入股票前賣出股票埋凯。
Example Two:
給你 n 個非負(fù)整數(shù) a1点楼，a2，...白对，an掠廓，每個數(shù)代表坐標(biāo)中的一個點(diǎn)?(i,?ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線甩恼，垂直線 i?的兩個端點(diǎn)分別為?(i,?ai) 和 (i, 0)蟀瞧。找出其中的兩條線，使得它們與?x?軸共同構(gòu)成的容器可以容納最多的水条摸。
說明：你不能傾斜容器悦污，且?n?的值至少為 2。
????????我在思考第一道題目的時候钉蒲，首先想到的是維護(hù)一個遞增棧切端，因?yàn)橹灰@取利潤，買入時價格必然低于賣出的價格子巾，那么只需要在遞增棧中取首尾數(shù)據(jù)即可得到最大利潤帆赢。但這種想法很快被我拋棄了，因?yàn)楫?dāng)遞增棧中突然出現(xiàn)一個極大的值线梗，則會被我們丟棄椰于，從而無法獲取最佳解。其次我想到仪搔，找到最值瘾婿，然后相減即可；但如果出現(xiàn)最小值在最大值的右側(cè)怎么辦烤咧？
????????那么假如第 i 天買入偏陪，第 j 天(j > i)賣出，如果第 j + 1 天的價格高于第 j 天煮嫌，那么在第 j + 1 天賣出肯定賺更多的錢笛谦；假如第 j + 1 天的價格低于第 j 天但高于第 i 天，那么就不需要考慮昌阿；但假如第 j + 1 天的價格低于第 i 天饥脑，那么第 j + 1 天以后的數(shù)據(jù)就和第 i 天無關(guān)恳邀，所以后面的結(jié)果只和第 j + 1 天有關(guān)。
? ? ? ? 而第二題如果也按照第一題的貪心思路去解灶轰，則會發(fā)現(xiàn)后面數(shù)值盡管比前面的小谣沸，但因?yàn)榈走呑冮L了，所以數(shù)值上無法確定大小笋颤。這似乎用貪心算法無法解決乳附，但我們可以換一種思路。使用兩個指針伴澄，分別指向頭 i 尾 j 赋除，然后依次逼近中心。假如 i < j ,那么如果i + 1 < i非凌，那么i + 1就不需要考慮了贤重，因?yàn)楦咦冃×说滓沧冃×耍灶^指針可以往中心走近一格清焕，如此貪心法完美解決該問題并蝗！
