Largest Rectangle in Histogram

题目原型：

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CjwvcD4KPHA+CkZvciBleGFtcGxlLDxicj4KR2l2ZW4gaGVpZ2h0ID0gPGNvZGU+WzIsMSw1LDYsMiwzXTwvY29kZT4sPGJyPgpyZXR1cm4gPGNvZGU+MTA8L2NvZGU+LjwvcD4KPHA+Crv5sb7LvMK3o7o8L3A+CjxwPgrTw9W7wLS05rSiobBoZWlnaHShsbrNobBpbmRleKGxo6yxo9ak1bvW0LXEuN+2yMrHtd3U9rXEo6zJqMPotcTKsbryu+Gz9s/W0tTPwsj91tbH6b/2o7o8L3A+CjxwPgoxLmhlaWdodFtjdXJyZW50XT5oZWlnaHRbc3RhY2sucG9wKCldPC9wPgo8cD4KtMvKscjr1btoZWlnaHS6zWluZGV4PC9wPgo8cD4KMi5oZWlnaHRbY3VycmVudF08aGVpZ2h0W3N0YWNrLnBvcCgpXTwvcD4KPHA+CrTLyrG8xsvjw+a7/aOss/bVu6OsuPzQwtfutPPD5rv9oaPWsbW90/a1vWhlaWdodFtjdXJyZW50XT5oZWlnaHRbc3RhY2sucG9wKCldPC9wPgo8cD4KMy5oZWlnaHRbY3VycmVudF09PWhlaWdodFtzdGFjay5wb3AoKV08cHJlIGNsYXNzPQ=="brush:java;"> public int largestRectangleArea(int[] height) { if (height == null || height.length == 0) return 0; int maxArea = 0; Stack stackHeight = new Stack (); Stack stackIndex = new Stack (); for (int i = 0; i < height.length; i++) { // case 1 if (stackHeight.isEmpty() || height[i] > stackHeight.peek()) { stackHeight.push(height[i]); stackIndex.push(i); } else if (height[i] < stackHeight.peek()) { // case 3 int lastIndex = 0; while (stackHeight.isEmpty() == false && height[i] < stackHeight.peek()) { lastIndex = stackIndex.pop(); int tempArea = stackHeight.pop() * (i - lastIndex); if (maxArea < tempArea) { maxArea = tempArea; } } //添加当前height和lastIndex进栈，至于为什么添加lastIndex，就是防止当前图形和前面的递增图形构成的面积比前面递增图形构成的面积大 stackHeight.push(height[i]); stackIndex.push(lastIndex); } } //处理栈中剩余元素 while (stackHeight.isEmpty() == false) { int tempArea = stackHeight.pop() * (height.length - stackIndex.pop()); if (tempArea > maxArea) { maxArea = tempArea; } } return maxArea; }