leetcode能用java刷嗎，[leetcode]84. Largest Rectangle in Histogram c語言

題目
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.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

思路
自己能想到就是O(n2)的解法（依次算每個高度能形成的最大面積），時間超過限制。學習了下其他人的解法http://blog.csdn.net/doc_sgl/article/details/11805519
從左依次遍歷高度數組，高度有增加時，就把每個下標依次存在棧中，當有斷崖出現時。就出棧并計算斷崖前的最大面積。理解棧中始終存著一個階梯狀的高度下標。

int largestRectangleArea(int* heights, int heightsSize) {int *stack = NULL, max = 0;int *dupHeights = NULL;int top = -1;int area = 0;int i;if(!heights || !heightsSize)return 0;stack = (int *)malloc(heightsSize * sizeof(int));if(!stack)return 0;dupHeights = (int *)malloc((heightsSize + 1) * sizeof(int));if(!dupHeights)return 0;/* 末尾追加高度0，以便最后出棧所有下標 */memcpy(dupHeights, heights, heightsSize * sizeof(int));dupHeights[heightsSize] = 0;for(i = 0; i < heightsSize + 1; ){if(top == -1 || dupHeights[i] >= dupHeights[stack[top]]){top++;stack[top] = i;i++;}else{     if(top == 0){area = dupHeights[stack[top]] * i;top--;}else{area = dupHeights[stack[top]] * (i - stack[top-1] - 1);top--;}if(max < area)max = area;}}free(stack);free(dupHeights);return max;
}

leetcode能用java刷嗎，Run Time:8ms