題目連結：
題目大意：
下圖為 12 個寬度為 1，長度不一的矩形所組成的長條圖：
而上圖能形成的最大矩形面積為 22 。
現給定 N ，代表有 N 個寬度為 1 的矩形排在一起，並給定那 N 個矩形的高度 H （1 ≦ N、H ≦ 10,000 ）。求能形成的最大矩形之面積。
範例輸入：
12
2
3
4
8
5
2
4
3
3
4
5
1
範例輸出：
22
解題思維：
我們可以用堆疊（Stack）得到所求，以題目的圖為例：
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
一開始的長度為 2、位置為 0，直接放入堆疊裡（由上至下為頂端到底端）：
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 3 、位置為 1 的矩形。沒有比堆疊頂端的矩形長，放入堆疊裡：
(3, 1)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 4 、位置為 2 的矩形。同理，放入堆疊裡：
(4, 2)
(3, 1)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 8 、位置為 3 的矩形。放入堆疊裡：
(8, 3)
(4, 2)
(3, 1)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 5 、位置為 4 的矩形。比堆疊頂端的長度小，移除頂端元素並計算面積：
(8, 3) → 8 × (4 - 3) = 8
並把現在的矩形放入堆疊，但是位置要存最後一個移除掉的矩形之位置（代表高度 5 的矩形可以從先前的位置延伸到這裡），因此：
(5, 3)
(4, 2)
(3, 1)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 2 、位置為 5 的矩形。同理，移掉 (5, 3)、(4, 2)、(3, 1)，得到了：
(5, 3) → 5 × (5 - 3) = 10。
(4, 2) → 4 × (5 - 2) = 12。
(3, 1) → 3 × (5 - 1) = 12。
因為跟頂端長度相同，不用放入堆疊裡：
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 4 、位置為 6 的矩形。堆疊為：
(4, 6)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 3 、位置為 7 的矩形。
(4, 6) → 4 × (7 - 6) ＝ 4。
堆疊為：
(3, 6)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 3 、位置為 8 的矩形。堆疊為
(3, 6)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 4 、位置為 9 的矩形。堆疊為：
(4, 9)
(3, 6)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 5 、位置為 A 的矩形。堆疊為：
(5, A)
(4, 9)
(3, 6)
(2, 0)
囗
囗
囗
囗囗 囗
囗囗囗 囗 囗囗
囗囗囗囗 囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗
囗囗囗囗囗囗囗囗囗囗囗囗
－－－－－－－－－－－－
０１２３４５６７８９ＡＢ
接下來是長度為 1 、位置為 B 的矩形。
(5, A) → 5 × (B - A) ＝ 5。
(4, 9) → 4 × (B - 9) ＝ 8。
(3, 6) → 3 × (B - 6) ＝ 15。
(2, 0) → 2 × (B - 0) ＝ 22。
堆疊為：
(1, 0)
最後清空堆疊：
(1, 0) → 1 × 12 ＝ 12。
而以上出現過最大的面積為 22，因此答案即為 22 。
所以我們可以看到當新的矩形長度小於堆疊頂端時，就移除頂端並計算面積。再把新的矩形放進去（但是位置是存最後一個移除的矩形之位置）。最後記得清空堆疊，即可求得解。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
