public int largestRectangleArea(int[] height) {
		// Start typing your Java solution below
		// DO NOT write main() function
		Stack<Pair> sta = new Stack<Pair>();
		if (height.length == 0)
			return 0;
		int res = 0;
		int i = 0;
		for (; i < height.length; i++) {
			int preH = sta.isEmpty() ? -1 : height[sta.peek().index];
			if (height[i] > preH) // situation 1
				sta.push(new Pair(i, i));
			else if (height[i] < preH) { // situation 3
				int last = 0;
				do {
					last = sta.pop().preIndex;
					res = Math.max((i - last) * preH, res);
				} while (!sta.isEmpty() && (preH = height[sta.peek().index]) >= height[i]);
				sta.push(new Pair(i, last));
			}
		}
		while (!sta.isEmpty()) {
			Pair cur = sta.pop();
			res = Math.max((i - cur.preIndex) * height[cur.index], res);
		}
		return res;
	}